Submission #1569953
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) struct uf{ int par[100005],ran[100005]; void init(){ for(int i=0;i<100005;i++){ par[i] = i; ran[i] = 0; } } int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x == y) return; if(ran[x] < ran[y]) par[x] = y; else{ par[y] = x; if(ran[x] == ran[y]) ran[x]++; } } }U; bool up[100005],col[100005]; int p[100005],num[100005],dw[100005],dep[100005],db[100005][18]; int S[100005]; vector<int>edge[100005],edge2[100005]; int val[100005]; int ty[100005],pos[100005],L[100005],N[100005],W[100005],C=1; int dfs(int v,int u){ int vs=-1,vi=-1; N[v]=C++; int sz=1; if(u == -1) dep[v] = 1; else dep[v] = dep[u]+1; db[v][0] = u; for(int i=0;i<edge[v].size();i++){ if(edge[v][i] == u) continue; int x = dfs(edge[v][i],v); if(x > vs){ vs = x; vi = edge[v][i]; } sz += x; } up[vi] = 1; dw[v] = vi;W[v] = C-1; return sz; } void dfs2(int v,int u){ for(int i=0;i<edge[v].size();i++){ if(edge[v][i] == u) continue; dfs2(edge[v][i],v); val[v] += val[edge[v][i]]; } } void make(int v,int u,int ko){ if(ko == 1) p[v] = v; else p[v] = p[u]; S[p[v]] = ko; num[v] = ko; bool U = 0; for(int i=0;i<edge[v].size();i++){ if(edge[v][i] == u) continue; if(dw[v] == edge[v][i]) {make(edge[v][i],v,ko+1);U=1;} else make(edge[v][i],v,1); } if(!U) L[v] = p[v]; } int lca(int u,int v){ if(dep[u] > dep[v]) swap(u,v); for(int i=0;i<18;i++){ if((((dep[v]-dep[u])>>i)&1)){ v = db[v][i]; } } assert(dep[u] == dep[v]); if(u == v) return u; for(int i=17;i>=0;i--){ if(db[u][i] != db[v][i]){ u = db[u][i]; v = db[v][i]; } } return db[u][0]; } struct hl{ int s; vector<int>seg,f,mem; void update(vector<int>hoge){ mem = hoge; } void make(int x){ for(int i=0;i<18;i++){ if(x < (1<<i)){ s = (1<<i); seg.resize(s*2,INF); f.resize(s*2,0); break; } } } void lazy(int k,int l,int r){ f[k*2+1] = f[k]; f[k*2+2] = f[k]; seg[k*2+1]-=f[k]; seg[k*2+2]-=f[k]; f[k] = 0; } void upd(int a,int b,int k,int l,int r,int a){ k+=s-1; seg[k] = min(seg[k],a); while(k){ k=(k-1)/2; seg[k]=min(seg[k*2+1],seg[k*2+2]); } } int add(int a,int b,int k,int l,int r,int num){ if(r<a||b<l)return seg[k]; if(a<=l&&r<=b){ f[k]+=num; seg[k]-=num; return seg[k]; } if(f[k]) lazy(k,l,r); return seg[k] = min(add(a,b,k*2+1,l,(l+r)/2,num),add(a,b,k*2+2,(l+r)/2+1,r,num)); } int query(int a,int b,int k,int l,int r){ if(r<a||b<l) return INF; if(a<=l && r<=b) return seg[k]; if(f[k]) lazy(k,l,r); return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2+1,r)); } int go(int k,int l,int r){ if(l==r)return l; if(f[k]) lazy(k,l,r); if(seg[k*2+1] == 1) return go(k*2+1,l,(l+r)/2); else return go(k*2+2,(l+r)/2+1,r); } void find(){ while(query(0,s-1,0,0,s-1) == 1){ pt_erase(go(0,0,s-1)); } } void add(int a,int b,int v){ add(a,b,0,0,s-1,v); } int query(int a,int b){ return query(a,b,0,0,s-1); } }dat[100005]; void make2(int cur){ int EN = L[cur]; vector<int>vi; while(1){ ty[cur] = EN; vi.pb(cur); if(cur == EN) break; else cur = db[cur][0]; } vi.pb(-1); reverse(vi.begin(),vi.end()); dat[EN].update(vi); dat[EN].make(); for(int i=1;i<vi.size();i++){ dat[EN].add(i,i,val[vi[i]]); } } queue<int>Q; void go(int cur,int en){ if(cur == en) return; if(!up[cur]){ val[cur]--; if(val[cur] == 1) Q.push(cur); go(db[cur][0],en); return; } else{ int x = num[cur]; int P = p[cur]; if(dep[P]>=dep[en]){ dat[P].add(1,x-1,-1); dat[P].find(); cur = p[cur]; go(cur,en); return; } else{ dat[P].upd(1+dep[en]-dep[P],x-1,-1); dat[P].find(); return; } } } multiset<P>SS[(1<<18)]; void update3(int a,int b,int c){ a+=(1<<17)-1; SS[a].insert(mp(b,c)); while(a>0){ a=(a-1)/2; SS[a].insert(mp(b,c)); } } int find3(int a,int b,int k,int l,int r,int num){ if(r<a||b<l) return -1; if(a<=l&&r<=b){ multiset<int>::iterator it = SS[k].upper_bound(mp(num,INF)); if(it != SS[k].begin()){ it--; if((*it).fi>=L) return (*it).sc;else return -1; } return -1; } return max(find3(a,b,k*2+1,l,(l+r)/2,num),find3(a,b,k*2+2,(l+r)/2+1,r,num)); } int find34(int a,int b,int k,int l,int r,int num){ if(r<a||b<l) return -1; if(a<=l&&r<=b){ multiset<int>::iterator it = SS[k].upper_bound(mp(num,-1)); if(it != SS[k].end()){ if((*it).fi>R) return (*it).sc; else return -1; } return -1; } return max(find34(a,b,k*2+1,l,(l+r)/2,num),find34(a,b,k*2+2,(l+r)/2+1,r,num)); } bool bad = 0; P p[100005]; int xxxx = 0; void pt_erase(int nu){ int A = ty[nu],B = num[nu];xxxx++; int x = dat[A].query(B,B,0,0,s-1); if(x != 1){ bad = 1; return; } dat[A].add(B,B,INF); int L = N[nu],R = W[nu]; int WW = find3(0,L-1,0,0,(1<<17)-1,R); int WW2 = find4(L,R,0,0,(1<<17)-1,R); WW=max(WW,WW2); int vv = lca(p[WW].fi,p[WW].sc); go(p[WW].fi,vv); go(p[WW].sc,vv); } int main(){ cin>>n; U.init(); rep(i,n-1){ int a,b;scanf("%d%d",&a,&b);edge[a].pb(b);edge[b].pb(a); } rep(i,n-1){ int a,b;scanf("%d%d",&a,&b);edge2[a].pb(b);edge2[b].pb(a); } dfs(1,-1); make(1,-1,1); for(int j=0;j<17;j++){ for(int i=1;i<=n;i++){ if(db[i][j] == -1){ db[i][j+1] = -1; } else{ db[i][j+1] = db[db[i][j]][j]; } } } for(int i=1;i<=n;i++){ for(int j=0;j<edge[i].size();j++){ if(i<edge[i][j]) continue; val[i]++; val[edge[i][j]]++; val[lca(i,edge[i][j])]-=2; } } dfs2(1,-1); int F=1; for(int i=1;i<=n;i++){ for(int j=0;j<edge2[i].size();j++){ if(i<edge2[i][j]) continue; int x = N[i],y = N[edge2[i][j]]; if(x>y) swap(x,y); update3(x,y,F); p[F]=mp(edge2[i][j],i); F++; } } for(int i=1;i<=n;i++){ if(L[i]) make2(i); } for(int i=2;i<=n;i++){ if(val[i] == 1){ pt_erase(i); while(Q.size()){ pt_erase(Q.front()); Q.pop(); } } } while(Q.size()){pt_erase(Q.front()); Q.pop(); } puts(!bad&&xxxx==n?"YES":"NO"); }
Submission Info
Submission Time | |
---|---|
Task | E - Blue and Red Tree |
User | IH19980412 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 6828 Byte |
Status | CE |
Compile Error
./Main.cpp:126:45: error: redefinition of ‘int a’ void upd(int a,int b,int k,int l,int r,int a){ ^ ./Main.cpp:126:15: note: ‘int a’ previously declared here void upd(int a,int b,int k,int l,int r,int a){ ^ ./Main.cpp: In member function ‘void hl::find()’: ./Main.cpp:159:24: error: ‘pt_erase’ was not declared in this scope pt_erase(go(0,0,s-1)); ^ ./Main.cpp: In function ‘void make2(int)’: ./Main.cpp:177:35: error: no matching function for call to ‘hl::make()’ dat[EN].update(vi); dat[EN].make(); ^ ./Main.cpp:109:7: note: candidate: void hl::make(int) void make(int x){ ^ ./Main.cpp:109:7: note: candidate expects 1 argument, 0 provided ./Main.cpp: In function ‘void go(int, int)’: ./Main.cpp:201:38: error: no matching function for call to ‘hl::upd(int, int, int)’ dat[P].upd(1+dep[en]-dep[P],x-1,-1); ^ ./Main.cpp:126:7: note: can...