Submission #814910

#TimeUsernameProblemLanguageResultExecution timeMemory
814910WonderfulWhaleJail (JOI22_jail)C++17
72 / 100
5062 ms271288 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define pii pair<int, int> #define st first #define nd second #define pb push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() struct SegTree { int T=1; vector<unordered_set<int>> t; void build(int n) { T=1; while(T<=n) T*=2; //cerr << "sz: "<< T<< "\n"; t.resize(2*T); //cerr << "rozmiar: "<< sz(t) << "\n"; for(int i=0;i<2*T;i++) t[i].clear(); } vector<int> query(int l, int r) { l+=T, r+=T; //cerr << "teraz: " << l << " " << r << "\n"; vector<int> ret; for(int x:t[l]) ret.pb(x); if(l!=r) for(int x:t[r]) ret.pb(x); while(l/2!=r/2) { if(l%2==0) for(int x:t[l+1]) ret.pb(x); if(r%2==1) for(int x:t[r-1]) ret.pb(x); l/=2; r/=2; } return ret; } void add(int x, int val) { x+=T; while(x) { t[x].insert(val); x/=2; } } void remove(int x, int val) { x+=T; while(x) { t[x].erase(val); x/=2; } } }; struct SegTree2 { int T = 1; vector<unordered_set<int>> t; void build(int n) { T=1; while(T<=n) T*=2; t.resize(2*T); for(int i=0;i<2*T;i++) t[i].clear(); } void add(int l, int r, int val) { l+=T, r+=T; t[l].insert(val); if(l!=r) t[r].insert(val); while(l/2!=r/2) { if(l%2==0) t[l+1].insert(val); if(r%2==1) t[r-1].insert(val); l/=2; r/=2; } } void remove(int l, int r, int val) { l+=T, r+=T; t[l].erase(val); if(l!=r) t[r].insert(val); while(l/2!=r/2) { if(l%2==0) t[l+1].erase(val); if(r%2==1) t[r-1].erase(val); l/=2; r/=2; } } vector<int> query(int x) { vector<int> ret; x+=T; while(x) { for(int y:t[x]) ret.pb(y); x/=2; } return ret; } }; vector<int> G[120009]; vector<int> G2[120009]; int tin[120009], tout[120009], T; int jp2[120009][20]; int deg[120009]; pii tab[120009]; int col[120009]; int dep[120009]; int p[120009]; int heavy[120009]; int pos[120009], P; int head[120009]; int dfs(int x, int y) { p[x] = y; dep[x] = dep[y]+1; int sz = 1, max_sz=0; tin[x] = ++T; jp2[x][0] = y; for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1]; for(int z:G[x]) if(z!=y) { int c_sz = dfs(z, x); //cout << x << " " << z << " " << c_sz << "\n"; //cout << max_sz << "\n"; sz += c_sz; if(c_sz>max_sz) { max_sz = c_sz; //cout << "setting heavy to: " << z << "\n"; heavy[x] = z; } } tout[x] = ++T; return sz; } void decompose(int x, int h) { head[x] = h; pos[x] = ++P; //cout << "pos: " << x << " " << pos[x] << "\n"; //cout << heavy[x] << "\n"; if(heavy[x]) { decompose(heavy[x], h); } for(int y:G[x]) { if(y!=p[x]&&y!=heavy[x]) decompose(y, y); } } bool is_ancestor(int x, int y) { return tin[x]<=tin[y]&&tout[x]>=tout[y]; } int lca(int x, int y) { if(is_ancestor(x, y)) return x; if(is_ancestor(y, x)) return y; for(int i=19;i>=0;i--) { if(!is_ancestor(jp2[x][i], y)) { x = jp2[x][i]; } } return jp2[x][0]; } bool is_on_path(int x, int a, int b) { return is_ancestor(a, x)&&is_ancestor(x, b); } bool f(int x, int a, int b) { int y = lca(a, b); //cerr << "lca: " << a << " " << b << " " << y << "\n"; //cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n"; return is_on_path(x, y, a)||is_on_path(x, y, b); } SegTree seg1; SegTree2 seg2; vector<int> hld_query(int a, int b) { //cout << "hld_query: " << a << " " << b << "\n"; vector<int> ret; for (; head[a] != head[b]; b=p[head[b]]) { if (dep[head[a]] > dep[head[b]]) swap(a, b); for(int x:seg1.query(pos[head[b]], pos[b])) ret.pb(x); } if (dep[a] > dep[b]) swap(a, b); for(int x:seg1.query(pos[a], pos[b])) ret.pb(x); return ret; } void hld_add(int a, int b, int val) { //cout << "hld_query: " << a << " " << b << "\n"; vector<int> ret; for (; head[a] != head[b]; b=p[head[b]]) { if (dep[head[a]] > dep[head[b]]) swap(a, b); seg2.add(pos[head[b]], pos[b], val); } if (dep[a] > dep[b]) swap(a, b); seg2.add(pos[a], pos[b], val); } void hld_remove(int a, int b, int val) { //cout << "hld_query: " << a << " " << b << "\n"; vector<int> ret; for (; head[a] != head[b]; b=p[head[b]]) { if (dep[head[a]] > dep[head[b]]) swap(a, b); seg2.remove(pos[head[b]], pos[b], val); } if (dep[a] > dep[b]) swap(a, b); seg2.remove(pos[a], pos[b], val); } bool dfs2(int x) { //cout << "dfs: " << x << "\n"; col[x] = 1; vector<int> v1 = hld_query(tab[x].st, tab[x].nd); for(int y:v1){ if(y==x) continue; //cout << "sprawdzam1: "<< y << "\n"; if(col[y]==1) return false; } for(int y:v1) { if(y==x) continue; if(!dfs2(y)) return false; } //cout << "v2 dla: "<< tab[x].nd << "\n"; vector<int> v2 = seg2.query(pos[tab[x].nd]); for(int y:v2) { if(y==x) continue; //cout << "sprawdzam2: "<< y << "\n"; if(col[y]==1) return false; } for(int y:v2) { if(y==x) continue; if(!dfs2(y)) return false; } col[x] = 2; seg1.remove(pos[tab[x].st], x); hld_remove(tab[x].st, tab[x].nd, x); return true; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int q=1; cin >> q; while(q--) { int n, m; cin >> n; for(int i=1;i<=n;i++) { G[i].clear(); head[i] = 0; heavy[i] = 0; dep[i] = 0; p[i] = 0; } for(int i=0;i<n-1;i++) { int a, b; cin >> a >> b; G[a].pb(b); G[b].pb(a); } tin[0] = T = 0; dfs(1, 0); P = 0; decompose(1, 1); tout[0] = T; cin >> m; for(int i=0;i<m;i++) { G2[i].clear(); deg[i] = 0; col[i] = 0; } seg1.build(n+9); seg2.build(n+9); for(int i=0;i<m;i++) { cin >> tab[i].st >> tab[i].nd; //cerr << pos[tab[i].st] << " " << tab[i].st << " " << tab[i].nd << "\n"; seg1.add(pos[tab[i].st], i); hld_add(tab[i].st, tab[i].nd, i); } bool ans = true; for(int i=0;i<m;i++) { if(!col[i]) { ans&=dfs2(i); } } if(ans) { cout << "Yes\n"; } else { cout << "No\n"; } } }
#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...