제출 #790238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790238		kshitij_sodani	Unique Cities (JOI19_ho_t5)	C++14	64 / 100	502 ms	61640 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'

int it[200001];
vector<int> adj[200001];
vector<int> adj2[200001];
int vis[200001];
int val[200001];
int ans[200001];
pair<int,int> ma={-1,-1};
int par2[200001];
void dfs(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no,levv+1);
		}
	}
}
void dfs2(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs2(j,no,levv+1);
		}
	}
}
int pp;
/*void dfs3(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	ans[no]=pp;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs3(j,no,levv+1);
		}
	}
}*/

map<int,int> ee;
int co=0;
void add(int i){
	ee[it[i]]++;
	if(ee[it[i]]==1){
		co++;
	}
}
void remove(int i){
	ee[it[i]]--;
	if(ee[it[i]]==0){
		co--;
	}
}
//set<pair<int,int>> zz;
int ma2[200001];
void dfs4(int no,int par=-1,int lev=0){
	ma2[no]=0;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs4(j,no,lev+1);
			ma2[no]=max(ma2[no],ma2[j]+1);
		}
	}
}

set<pair<int,int>> zz;
pair<int,int> tree[4*200001];
int lazy[4*200001];
void build(int no,int l,int r){
	tree[no]={0,r-l+1};
	lazy[no]=0;
	if(l==r){
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
	}

}
void push(int no,int l,int r){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];

	}
	lazy[no]=0;

}
pair<int,int> merge(pair<int,int> x,pair<int,int> y){
	if(x.a<y.a){
		return x;
	}
	if(y.a<x.a){
		return y;
	}
	return {x.a,x.b+y.b};
}
void update(int no,int l,int r,int aa,int bb,int x){
	if(lazy[no]!=0){
		push(no,l,r);
	}
	if(bb<l or r<aa or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]=x;
		push(no,l,r);
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x);
		update(no*2+2,mid+1,r,aa,bb,x);
		tree[no]=merge(tree[no*2+1],tree[no*2+2]);
	}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
	push(no,l,r);

	if(r<aa or l>bb or aa>bb){
		return {1e8,0};
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	int mid=(l+r)/2;
	pair<int,int> x=query(no*2+1,l,mid,aa,bb);
	pair<int,int> y=query(no*2+2,mid+1,r,aa,bb);
	tree[no]=merge(tree[no*2+1],tree[no*2+2]);
	return merge(x,y);

}
int n,m;
void dfs5(int no,int par=-1,int lev=0){
	vector<pair<int,int>> mm;
	//cout<<no<<";";

	for(auto j:adj2[no]){
		if(j!=par){
			mm.pb({ma2[j],j});
		}
	}
	sort(mm.begin(),mm.end());
	reverse(mm.begin(),mm.end());
	vector<pair<int,int>> kk;
	//add(no);
	//zz.insert({lev,no});
	int ind3=-1;
	for(auto j:mm){
		ind3++;
		int ne=-1;
		if(ind3==0){
			if(mm.size()>=2){
				ne=mm[1].a;
			}
		}
		else if(ind3==1){
			ne=mm[0].a;;
		}
		if(ne>=0 and lev>0){
			ne++;
			update(0,0,n-1,max(lev-ne,0),max(lev-1,0),1);
			kk.pb({max(lev-ne,0),max(lev-1,0)});
			/*auto jj=zz.lower_bound({lev-ne,-1});
			vector<pair<int,int>> ll;
			while(jj!=zz.end()){
				if((*jj).a>=lev){
					break;
				}
				remove((*jj).b);
				ll.pb(*jj);
				jj++;
			}
			for(auto ii:ll){
				kk.pb(ii);
				zz.erase(ii);
			}*/
		}
		dfs5(j.b,no,lev+1);
	}
	if(mm.size()==1 and lev>0){
		int ne=mm[0].a+1;
		update(0,0,n-1,max(lev-ne,0),max(lev-1,0),1);
		kk.pb({max(lev-ne,0),max(lev-1,0)});
		/*auto jj=zz.lower_bound({lev-ne,-1});
		vector<pair<int,int>> ll;
		while(jj!=zz.end()){
			if((*jj).a>=lev){
				break;
			}
			remove((*jj).b);
			ll.pb(*jj);
			jj++;
		}
		for(auto ii:ll){
			kk.pb(ii);
			zz.erase(ii);
		}*/
	}
	//zz.erase({lev,no});
	//remove(no);

	ans[no]=co;
	pair<int,int> x=query(0,0,n-1,0,lev-1);
	if(x.a==0){
		ans[no]+=x.b;
	}
	//lev-1 to lev-ma[no]
	
	for(auto j:kk){
		update(0,0,n-1,j.a,j.b,-1);
	//	zz.insert(j);
		//add(j.b);
	}
}
int ha=0;

void solve(vector<int> ss){
	set<pair<int,int>> tt;
	ee.clear();
	co=0;

	//map of present colours
	int ind=ss.size();
	for(int i=0;i<ss.size();i++){
		tt.insert({i,ss[i]});
	}
	for(int i=ss.size()-1;i>=0;i--){

		auto j=tt.lower_bound({i+1,-1});
		vector<pair<int,int>> kk;
		while(j!=tt.end()){
			if((*j).a>i+val[ss[i]]){
				break;
			}
			if((*j).a>=ind){
				remove((*j).b);
			}
			kk.pb(*j);
			j++;
			/*if(ss[0]==1){
				cout<<(*j).b<<"?"<<endl;

			}*/
		}
		for(auto j:kk){
			tt.erase(j);
		}
		if(i<(int)(ss.size())-i-1){
			int ind2=2*i+1;
			while(ind>ind2){
				ind--;
				if(tt.find({ind,ss[ind]})!=tt.end()){
					add(ss[ind]);
				}
			}
			ans[ss[i]]=co;
			//continue;
		/*	if(ss[i]==0){
				for(auto jj:ee){
					cout<<jj.a<<",,"<<jj.b<<endl;
				}
			}*/
			dfs4(ss[i]);
		/*	if(ss[i]==0){
				cout<<ma2[ss[i]]<<"?"<<endl;
			}*/
			dfs5(ss[i]);
		//	cout<<endl;
			//ans[ss[i]]=co;
		}
		if(i==(int)ss.size()-i-1 and ha==0){
			ha=1;
			dfs4(ss[i]);
			dfs5(ss[i]);

		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	dfs(0);
	int x=ma.b;
	ma={-1,-1};
	dfs(x);
	dfs2(x);

	vector<int> ss;
	int cur=ma.b;
	while(true){
		ss.pb(cur);
		cur=par2[cur];
		if(cur==-1){
			break;
		}
	}
	for(auto j:ss){
		vis[j]=1;
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(vis[i]+vis[j]<2){
				adj2[i].pb(j);
			}
		}
	}

	for(auto j:ss){
		ma={-1,-1};
		dfs2(j);
		val[j]=ma.a;
	//cout<<j<<":"<<ma.a<<endl;
	}
	build(0,0,n-1);

	solve(ss);
	reverse(ss.begin(),ss.end());
	solve(ss);
/*	for(auto j:ss){
		pp=ans[j];
		dfs3(j);
	}*/
	for(int i=0;i<n;i++){
		if(m==1){
			cout<<min(ans[i],1)<<endl;
			continue;
		}
		cout<<ans[i]<<endl;
	}


	

	


	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t5.cpp: In function 'void solve(std::vector<int>)':
joi2019_ho_t5.cpp:233:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32