Submission #163325

#	Time	Username	Problem	Language	Result	Execution time	Memory
163325		HungAnhGoldIBO2020	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	567 ms	49396 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
int cnt[N],dp[N],color[N],level[N],ans[N],pts=0,dem=0;
vector<int> adj[N];
stack<int> lis;
void add(int x){
	cnt[color[x]]++;
	if(cnt[color[x]]==1){
		dem++;
	}
	lis.push(x);
}
void del(){
	assert(lis.size());
	int x=lis.top();
	lis.pop();
	cnt[color[x]]--;
	if(cnt[color[x]]==0){
		dem--;
	}
}
void dfs(int x,int p){
	if(level[x]>=level[pts]){
		pts=x;
	}
	dp[x]=level[x];
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i]!=p){
			level[adj[x][i]]=level[x]+1;
			dfs(adj[x][i],x);
			dp[x]=max(dp[x],dp[adj[x][i]]);
		}
	}
}
bool cmp(pair<int,int> x,pair<int,int> y){
	return x.first>y.first;
}
void dfs1(int x,int p){
	if(x!=p){
		add(p);
	}
	vector<pair<int,int> > wow;
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i]!=p){
			wow.push_back({dp[adj[x][i]],adj[x][i]});
		}
	}
	sort(wow.begin(),wow.end(),cmp);
	for(int i=0;i<wow.size();i++){
		int to=0;
		if(i==0){
			if(wow.size()>1){
				to=wow[1].first;
			}
		}
		else{
			to=wow[0].first;
		}
		while(lis.size()&&to-level[x]>=level[x]-level[lis.top()]){
			del();
		}
		dfs1(wow[i].second,x);
	}
	while(lis.size()&&dp[x]-level[x]>=level[x]-level[lis.top()]){
		del();
	}
	ans[x]=max(ans[x],dem);
//	cout<<x<<' '<<lis.size()<<' '<<level[x]<<' '<<dp[x]<<' '<<dem<<" cac\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,m;
	cin>>n>>m;
	for(i=1;i<n;i++){
		cin>>j>>k;
		adj[j].push_back(k);
		adj[k].push_back(j);
	}
	for(i=1;i<=n;i++){
		cin>>color[i];
	}
	dfs(1,1);
	for(j=0;j<2;j++){
//		cout<<j<<endl;
		i=pts;
		level[i]=0;
		dfs(i,i);
		dfs1(i,i);
		assert(lis.size()==0);
	}
	for(i=1;i<=n;i++){
		cout<<ans[i]<<'\n';
	}
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void dfs1(int, int)':
joi2019_ho_t5.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<wow.size();i++){
              ~^~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:74:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,m;
              ^

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