Submission #163275

#	Time	Username	Problem	Language	Result	Execution time	Memory
163275		HungAnhGoldIBO2020	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	399 ms	46328 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
const int LOG=19;
int ar[N];
int ans[N][2],pts[2],level[N][2],ancestor[N][LOG][2],cnt=0;
bool used[N][2];
//int pos[N];
//set<int> color[N];
set<int> color;
vector<int> lis[N],adj[N];
void dfs(int x,int p){
	if(cnt<2){
		if(level[x][0]>=level[pts[cnt]][0]){
			pts[cnt]=x;
		}
	}
	lis[level[x][0]].push_back(x);
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i]!=p){
			level[adj[x][i]][0]=level[x][0]+1;
			dfs(adj[x][i],x);
		}
	}
}
void dfs1(int x,int p){		//right now cnt is above
	int idx=0,i;
	for(i=1;i<LOG;i++){
		ancestor[x][i][cnt]=ancestor[ancestor[x][i-1][cnt]][i-1][cnt];
	}
	for(i=0;i<adj[x].size();i++){
		if(adj[x][i]!=p){
			level[adj[x][i]][cnt]=level[x][cnt]+1;
			ancestor[adj[x][i]][0][cnt]=x;
			dfs1(adj[x][i],x);
//			if(color[pos[adj[x][i]]].size()>color[idx].size()){
//				idx=pos[adj[x][i]];
//			}
		}
	}
//	pos[x]=idx;
//	for(i=0;i<adj[x].size();i++){
//		if(adj[x][i]!=p&&pos[adj[x][i]]!=idx){
//			for(auto ite=color[pos[adj[x][i]]].begin();ite!=color[pos[adj[x][i]]].end();ite++){
//				color[pos[x]].insert(*ite);
//			}
//		}
//	}
//	ans[x][cnt]=color[pos[x]].size();
//	if(used[x][cnt]){
//		color[pos[x]].insert(ar[x]);
//	}
}
int findd(int x,int k,int idx){
	while(k){
		int y=__lg(k);
		x=ancestor[x][y][idx];
		k-=(1<<y);
	}
	return x;
}
int LCA(int x,int y,int idx){
	if(level[x][idx]>level[y][idx]){
		x=findd(x,level[x][idx]-level[y][idx],idx);
	}
	y=findd(y,level[y][idx]-level[x][idx],idx);
	if(x==y){
		return x;
	}
	for(int i=LOG-1;i>=0;i--){
		if(ancestor[x][i][idx]!=ancestor[y][i][idx]){
			x=ancestor[x][i][idx],y=ancestor[y][i][idx];
		}
	}
	return ancestor[x][0][idx];
}
int dis(int x,int y){
	return level[x][0]+level[y][0]-2*level[LCA(x,y,0)][0];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k,l;
	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>>ar[i];
	}
	dfs(1,1);
	cnt++;
	level[pts[0]][0]=0;
	for(i=0;i<n;i++){
		lis[i].clear();
	}
	//this maybe confusing ofter, but... it's ok because level using dfs is 0
	dfs(pts[0],pts[0]);
	for(i=0;i<n;i++){
		if(lis[i].size()==1){
			used[lis[i][0]][0]=true;
//			cout<<lis[i][0]<<' ';
		}
		lis[i].clear();
	}
//	cout<<endl;
	level[pts[1]][0]=0;
	cnt++;
	dfs(pts[1],pts[1]);
	for(i=0;i<n;i++){
		if(lis[i].size()==1){
			used[lis[i][0]][1]=true;
		}
		lis[i].clear();
	}
	level[pts[0]][0]=0;
	cnt=0;
	dfs1(pts[0],pts[0]);
	j=pts[1];
	while(j){
		ans[j][0]=color.size();
		if(used[j][0]){
			color.insert(ar[j]);
		}
		j=ancestor[j][0][0];
	}
//	for(i=1;i<=n;i++){
//		cout<<ans[i][cnt]<<' ';
//	}
//	cout<<endl;
	cnt++;
//	for(i=0;i<n;i++){
//		color[i].clear();
//	}
	level[pts[1]][1]=0;
	dfs1(pts[1],pts[1]);
	color.clear();
	j=pts[0];
	while(j){
		ans[j][1]=color.size();
		if(used[j][1]){
			color.insert(ar[j]);
		}
		j=ancestor[j][0][1];
	}
//	for(i=1;i<=n;i++){
//		cout<<ans[i][cnt]<<' ';
//	}
//	cout<<endl;
//	cout<<dis(1,5)<<endl;
	for(i=1;i<=n;i++){
		j=dis(i,pts[0]);
		k=dis(i,pts[1]);
		if(j==k){
			cout<<0<<'\n';
			continue;
		}
		if(j<k){
//			cout<<findd(pts[1],k-j,0)<<" cac\n";
			cout<<ans[findd(pts[1],k-j,0)][0]<<'\n';
		}
		else{
//			cout<<findd(pts[0],j-k,1)<<" cac\n";
			cout<<ans[findd(pts[0],j-k,1)][1]<<'\n';
		}
	}
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:19: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:31:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<adj[x].size();i++){
          ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:27:6: warning: unused variable 'idx' [-Wunused-variable]
  int idx=0,i;
      ^~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:83:16: warning: unused variable 'l' [-Wunused-variable]
  int n,m,i,j,k,l;
                ^

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