Submission #790227

# Submission time Handle Problem Language Result Execution time Memory
790227 2023-07-22T12:49:10 Z kshitij_sodani Unique Cities (JOI19_ho_t5) C++14
0 / 100
296 ms 33200 KB
#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;
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){
			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);
	}
	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);
		}
	}
	zz.erase({lev,no});
	remove(no);

	ans[no]=co;

	//lev-1 to lev-ma[no]
	
	for(auto j:kk){
		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);
	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;
}

Compilation message

joi2019_ho_t5.cpp: In function 'void solve(std::vector<int>)':
joi2019_ho_t5.cpp:157:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 21612 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 33200 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -