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...