Submission #735078

#TimeUsernameProblemLanguageResultExecution timeMemory
735078cadmiumskyJail (JOI22_jail)C++17
60 / 100
1008 ms473268 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; const int nmax = 12e4 + 5; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; pii chains[nmax]; namespace Tree { int pin[nmax], pout[nmax], area[nmax], inp; int p[nmax], jump[nmax], d[nmax]; int pch[nmax]; namespace G { vector<vector<int>> g; vector<int> occ; // Low level int newnode() { g.emplace_back(); occ.emplace_back(0); return sz(g) - 1; } void addedge(int x, int y) { if(x != 0 && y != 0) g[x].emplace_back(y); } bool dfs(int node) { if(occ[node] == 2) return 0; if(occ[node] == 1) return 1; occ[node] = 1; bool ok = 0; for(auto x : g[node]) ok |= dfs(x); occ[node] = 2; return ok; } bool findcyc() { bool found = 0; for(int i = 0; !found && i < sz(g); i++) { found |= dfs(i); } return found; } // High Level int inspre[16][nmax]; // sus in jos int dinspre[16][nmax]; // jos in sus int lg2[nmax]; void init(vector<int> T, vector<int> A) { int n = sz(T); for(int i = 2; i < n; i++) lg2[i] = lg2[i >> 1] + 1; for(int i = 0; i < n; i++) inspre[0][i] = T[i]; for(int step = 1; step < 16; step++) { for(int i = 0; i + (1 << step) <= n; i++) { inspre[step][i] = newnode(); addedge(inspre[step][i], inspre[step - 1][i]); addedge(inspre[step][i], inspre[step - 1][i + (1 << step - 1)]); } } n = sz(A); for(int i = 0; i < n; i++) dinspre[0][i] = A[i]; for(int step = 1; step < 16; step++) { for(int i = 0; i + (1 << step) <= n; i++) { dinspre[step][i] = newnode(); addedge(dinspre[step - 1][i], dinspre[step][i]); addedge(dinspre[step - 1][i + (1 << step - 1)], dinspre[step][i]); } } return; } void pushdown(int X, int l, int r) { int step = lg2[r - l + 1]; addedge(X, inspre[step][l]); addedge(X, inspre[step][r - (1 << step) + 1]); //cerr << X << " --> " << l << ", " << r << '\n'; } void pushup(int X, int l, int r) { int step = lg2[r - l + 1]; addedge(dinspre[step][r - (1 << step) + 1], X); addedge(dinspre[step][l], X); //cerr << X << " <-- " << l << ", " << r << '\n'; } void push(int X, int l, int r, int pass = 0) { if(r < l) return; int mid = -1; if(pass == 0) mid = pin[chains[X].first]; else if(pass == 1) mid = pin[chains[X].second]; if(l <= mid && mid <= r) { push(X, l, mid - 1, pass + 1), push(X, mid + 1, r, pass + 1); return; } if(pass != 2) { push(X, l, r, pass + 1); return; } pushup(X, l, r); pushdown(X, l, r); return; } void init(int n) { g.clear(); occ.clear(); g.resize(n + 1); occ.resize(n + 1, 0); } } vector<int> g[nmax]; void initstd(int node, int f) { p[node] = f; jump[node] = f; d[node] = d[f] + 1; if(d[jump[f]] - d[jump[jump[f]]] == d[f] - d[jump[f]]) jump[node] = jump[jump[f]]; //cerr << node << '>' << jump[node] << '\n'; area[node] = 1; for(auto x : g[node]) { if(x == f) continue; initstd(x, node); area[node] += area[x]; } return; } bool isanc(int x, int y) { return pin[x] <= pin[y] && pout[y] <= pout[x]; } int lca(int x, int y) { while(!isanc(x, y)) { if(!isanc(jump[x], y)) x = jump[x]; x = p[x]; } return x; } namespace HLD { void initp(int node, int f) { pin[node] = inp++; //cerr << node << ' ' << inp - 1 << '\n'; int atrs = -1; for(auto x : g[node]) { if(x == f) continue; if(atrs == -1 || area[atrs] < area[x]) atrs = x; } if(atrs == -1) { pout[node] = inp - 1; return; } pch[atrs] = pch[node]; initp(atrs, node); for(auto x : g[node]) { if(x == f || x == atrs) continue; pch[x] = x; initp(x, node); } pout[node] = inp - 1; return; } void pushQ(int x, int y, int X) { if(isanc(x, y) && x != y) return; //cerr << X << '\t' << x << ' ' << y << '\n'; if(pch[x] == pch[y]) { G::push(X, pin[y], pin[x]); return; } G::push(X, pin[pch[x]], pin[x]); pushQ(p[pch[x]], y, X); } } void init(int n) { inp = 0; for(int i = 0; i <= n; i++) g[i].clear(); } } void driver() { int n, m; cin >> n; Tree::init(n); for(int i = 1, x, y; i < n; i++) { cin >> x >> y; Tree::g[x].emplace_back(y); Tree::g[y].emplace_back(x); } Tree::g[0].emplace_back(1); Tree::g[1].emplace_back(0); Tree::initstd(0, 0); Tree::HLD::initp(0, 0); cin >> m; vector<int> ends(n + 1), starts(n + 1); for(int i = 1, S, T; i <= m; i++) { cin >> S >> T; starts[Tree::pin[S]] = i; ends[Tree::pin[T]] = i; chains[i] = pii{S, T}; } //for(auto x : ends) cerr << x << ' '; cerr << '\n'; //for(auto x : starts) cerr << x << ' '; cerr << '\n'; Tree::G::init(m); Tree::G::init(ends, starts); for(int i = 1, S, T; i <= m; i++) { tie(S, T) = chains[i]; int L = Tree::lca(S, T); Tree::HLD::pushQ(S, L, i); Tree::HLD::pushQ(T, L, i); Tree::G::pushdown(i, Tree::pin[S], Tree::pin[S]); Tree::G::pushup(i, Tree::pin[T], Tree::pin[T]); } cout << (Tree::G::findcyc()? "No\n" : "Yes\n"); } signed main() { int T; cin >> T; while(T--) driver(); } /** Anul asta se da centroid. -- Surse oficiale */

Compilation message (stderr)

jail.cpp: In function 'void Tree::G::init(std::vector<int>, std::vector<int>)':
jail.cpp:70:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |             addedge(inspre[step][i], inspre[step - 1][i + (1 << step - 1)]);
      |                                                                 ~~~~~^~~
jail.cpp:80:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   80 |             addedge(dinspre[step - 1][i + (1 << step - 1)], dinspre[step][i]);
      |                                                 ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...