제출 #790831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790831		kshitij_sodani	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	333 ms	41044 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;
int ne[200001];
vector<pair<int,int>> pre2[200001];
void dfs5(int no,int par=-1,int lev=0,int zz2=1){
	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){
			ne++;
			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,ind3==0);
	}
	if(mm.size()){
		ne[no]=mm[0].b;

	}
	else{
		ne[no]=-1;
	}
	if(mm.size()==1){
		int ne=mm[0].a+1;
		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);
		}
	}
	
	pre2[no]=kk;
	if(zz.find({lev,no})!=zz.end()){
		zz.erase({lev,no});
		remove(no);
	}
	
 
	ans[no]=co;
 
	//lev-1 to lev-ma[no]
	if(zz2==1){
		int cur=no;
		while(cur>=0){
			for(auto j:pre2[no]){
				if(j.a<lev){
					zz.insert(j);
					add(j.b);
				}
			}
			break;
			cur=ne[cur];
		}
	}
}
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);
	int n,m;
	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;
	}
 
	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++){
		cout<<ans[i]<<endl;
	}
 
 
	
 
	
 
 
	return 0;
}

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

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

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