Submission #121337

#	Time	Username	Problem	Language	Result	Execution time	Memory
121337		imyujin	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	680 ms	34040 KiB

joi2019_ho_t5

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 200005

int N, M;
int A[MAXN], B[MAXN], C[MAXN];
vector<int> E[MAXN];
int dep[MAXN], par[MAXN], uni[MAXN], mxdep[MAXN][2], mxn[MAXN];
int cnts[MAXN];
int spe;
int ans[MAXN];

int guni(int x){
	if(uni[x]==x) return x;
	return uni[x]=guni(uni[x]);
}

void dfs(int x){
	//printf("dfs(%d)\n", x);
	mxdep[x][0]=mxdep[x][1]=dep[x];
	for(auto a:E[x]) if(dep[a]==-1){
		dep[a]=dep[x]+1;
		par[a]=x;
		dfs(a);
		if(mxdep[a][0]>mxdep[x][1]) mxdep[x][1]=mxdep[a][0];
		if(mxdep[x][1]>mxdep[x][0]){
			swap(mxdep[x][0], mxdep[x][1]);
			mxn[x]=a;
		}
	}
}

void gdfs(int x){
	//printf("gdfs(%d)\n", x);
	for(int i=0; i<=N; i++){
		dep[i]=-1;
		mxn[i]=0;
		par[i]=0;
	}
	dep[x]=0;
	dfs(x);
}

void cover(int x, int d){
	//printf("cover(x=%d, d=%d)\n", x, d);
	for(; x!=0&&dep[x]>=d; x=guni(par[x])){
		if(uni[x]==x&&--cnts[C[x]]==0) spe--;
		uni[x]=guni(par[x]);
	}
}

void dfs2(int x){
	/*
	printf("dfs2(%d), spe=%d\n", x, spe);
	printf("uni=[");
	for(int i=1; i<=N; i++) printf("%d ", uni[i]);
	printf("]\ncnts=[");
	for(int i=1; i<=M; i++) printf("%d ", cnts[i]);
	printf("]\n");
	*/
	//for(int i=1; i<=M; i++) printf("cnts[%d]=%d\n", i, cnts[i]);
	if(++cnts[C[x]]==1) spe++;
	if(dep[x]!=mxdep[x][0]){
		cover(guni(par[x]), 2*dep[x]-mxdep[x][1]);
		dfs2(mxn[x]);
		if(uni[x]!=x){
			uni[x]=x;
			if(++cnts[C[x]]==1) spe++;
		}
		cover(guni(par[x]), 2*dep[x]-mxdep[x][0]);
		for(auto a:E[x]) if(a!=par[x]&&a!=mxn[x]){
			dfs2(a);
			if(uni[x]!=x){
				uni[x]=x;
				if(++cnts[C[x]]==1) spe++;
			}
		}
	}
	if(uni[x]==x&&--cnts[C[x]]==0) spe--;
	ans[x]=max(ans[x], spe);
}

void solve(int x){
	//printf("solve(%d)\n", x);
	for(int i=0; i<=N; i++) uni[i]=i;
	spe=0;
	for(int i=1; i<=M; i++) cnts[i]=0;
	dfs2(x);
}

int main(){
	int X=1, Y=1;

	scanf("%d%d", &N, &M);
	for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
	for(int i=1; i<=N; i++) scanf("%d", C+i);

	for(int i=0; i<N-1; i++){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}

	gdfs(1);
	for(int i=1; i<=N; i++) if(dep[i]>dep[X]) X=i;
	gdfs(X);
	for(int i=1; i<=N; i++) if(dep[i]>dep[Y]) Y=i;
	//printf("X=%d, Y=%d\n", X, Y);
	//for(int i=1; i<=N; i++) printf("mxdep[%d]=%d, mxn[%d]=%d\n", i, mxdep[i][0], i, mxn[i]);
	solve(X);
	gdfs(Y);
	solve(Y);

	for(int i=1; i<=N; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:99:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
                           ~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:100:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", C+i);
                          ~~~~~^~~~~~~~~~~

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