From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- graph/reroot.cpp | 62 -------------------------------------------------------- 1 file changed, 62 deletions(-) delete mode 100644 graph/reroot.cpp (limited to 'graph/reroot.cpp') diff --git a/graph/reroot.cpp b/graph/reroot.cpp deleted file mode 100644 index 4c6a748..0000000 --- a/graph/reroot.cpp +++ /dev/null @@ -1,62 +0,0 @@ -// Usual Tree DP can be broken down in 4 steps: -// - Initialize dp[v] = identity -// - Iterate over all children w and take a value for w -// by looking at dp[w] and possibly the edge label of v -> w -// - combine the values of those children -// usually this operation should be commutative and associative -// - finalize the dp[v] after iterating over all children -struct Reroot { - using T = ll; - - // identity element - T E() {} - // x: dp value of child - // e: index of edge going to child - T takeChild(T x, int e) {} - T comb(T x, T y) {} - // called after combining all dp values of children - T fin(T x, int v) {} - - vector>> g; - vector ord, pae; - vector dp; - - T dfs(int v) { - ord.push_back(v); - for (auto [w, e] : g[v]) { - g[w].erase(find(all(g[w]), pair(v, e^1))); - pae[w] = e^1; - dp[v] = comb(dp[v], takeChild(dfs(w), e)); - } - return dp[v] = fin(dp[v], v); - } - - vector solve(int n, vector> edges) { - g.resize(n); - for (int i = 0; i < n-1; i++) { - g[edges[i].first].emplace_back(edges[i].second, 2*i); - g[edges[i].second].emplace_back(edges[i].first, 2*i+1); - } - pae.assign(n, -1); - dp.assign(n, E()); - dfs(0); - vector updp(n, E()), res(n, E()); - for (int v : ord) { - vector pref(sz(g[v])+1), suff(sz(g[v])+1); - if (v != 0) pref[0] = takeChild(updp[v], pae[v]); - for (int i = 0; i < sz(g[v]); i++){ - auto [u, w] = g[v][i]; - pref[i+1] = suff[i] = takeChild(dp[u], w); - pref[i+1] = comb(pref[i], pref[i+1]); - } - for (int i = sz(g[v])-1; i >= 0; i--) { - suff[i] = comb(suff[i], suff[i+1]); - } - for (int i = 0; i < sz(g[v]); i++) { - updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); - } - res[v] = fin(pref.back(), v); - } - return res; - } -}; -- cgit v1.2.3