oj.uz

Submission #121332

# Submission time Handle Problem Language Result Execution time Memory
121332 2019-06-26T10:40:58 Z imyujin Unique Cities (JOI19_ho_t5) C++14
0 / 100
 314 ms 17272 KB 
#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=1; i<=N; i++){
		dep[i]=-1;
		mxn[i]=0;
		par[i]=0;
	}
	dep[x]=0;
	dfs(x);
}

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

void dfs2(int x){
	//printf("dfs2(%d), spe=%d\n", x, spe);
	//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]);
		uni[x]=x;
		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(--cnts[C[x]]==0) spe--;
	ans[x]=max(ans[x], spe);
}

void solve(int x){
	//printf("solve(%d)\n", x);
	for(int i=1; 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

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:87: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:88: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:89: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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 7 ms 5248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 13420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 17272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 7 ms 5248 KB Output isn't correct
3 Halted 0 ms 0 KB -