oj.uz

Submission #121229

# Submission time Handle Problem Language Result Execution time Memory
121229 2019-06-26T08:39:32 Z 임유진(#2971) Unique Cities (JOI19_ho_t5) C++14
0 / 100
 513 ms 20948 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 200000

int N, M;
int A[MAXN], B[MAXN], C[MAXN];
vector<int> e[MAXN];
int dep[MAXN], mxdep[MAXN][2];
int seg[MAXN*4], cnt[MAXN*4];
int ans[MAXN];

void mkseg(int idx, int l, int r){
	seg[idx]=0;
	cnt[idx]=r-l+1;
	if(l<r){
		int m=(l+r)/2;
		mkseg(idx*2, l, m);
		mkseg(idx*2+1, m+1, r);
	}
}

void updseg(int idx, int l, int r, int x, int y, int z){
	//if(idx==1) printf("updseg(%d %d %d)\n", x, y, z);
	if(x>y) return;
	if(x<=l&&r<=y) seg[idx]+=z;
	else if(l<=y&&x<=r){
		int m=(l+r)/2;
		updseg(idx*2, l, m, x, y, z);
		updseg(idx*2+1, m+1, r, x, y, z);
		if(seg[idx*2]<seg[idx*2+1]){
			seg[idx]=seg[idx*2];
			cnt[idx]=cnt[idx*2];
		}
		else if(seg[idx*2]==seg[idx*2+1]){
			seg[idx]=seg[idx*2];
			cnt[idx]=cnt[idx*2]+cnt[idx*2+1];
		}
		else{
			seg[idx]=seg[idx*2+1];
			cnt[idx]=cnt[idx*2+1];
		}
	}
}

int gseg(int idx, int l, int r, int x, int y){
	if(seg[idx]>0) return 0;
	if(x<=l&&r<=y) return cnt[idx];
	if(r<x||y<l) return 0;
	int m=(l+r)/2;
	return gseg(idx*2, l, m, x, y)+gseg(idx*2+1, m+1, r, x, y);
}

void dfs1(int x){
	mxdep[x][0]=dep[x];
	mxdep[x][1]=0;
	for(auto a:e[x]) if(dep[a]==-1){
		dep[a]=dep[x]+1;
		dfs1(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]);
	}
}

void dfs2(int x){
	//printf("dfs2(%d)\n", x);
	updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, 1);
	ans[x]=max(ans[x], gseg(1, 0, N-1, 0, dep[x]));
	if(e[x].size()-(dep[x]==0?0:1)>1){
		//printf("x=%d\n", x);
		for(auto a:e[x]) if(dep[a]>dep[x]&&mxdep[a][0]!=mxdep[x][0]) dfs2(a);
		//printf("x=%d*\n", x);
		updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, -1);
		updseg(1, 0, N-1, 2*dep[x]-mxdep[x][1], dep[x]-1, 1);
		for(auto a:e[x]) if(dep[a]>dep[x]&&mxdep[a][0]==mxdep[x][0]) dfs2(a);
		updseg(1, 0, N-1, 2*dep[x]-mxdep[x][1], dep[x]-1, -1);
	}
	else{
		updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, -1);
		for(auto a:e[x]) if(dep[a]>dep[x]) dfs2(a);
	}
}

int main(){
	int X, Y;

	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]);
	}
	for(int i=1; i<=N; i++) dep[i]=-1;
	dep[1]=0;
	dfs1(1);

	X=1;
	for(int i=1; i<=N; i++) if(dep[i]>dep[X]) X=i;
	for(int i=1; i<=N; i++) dep[i]=-1;
	dep[X]=0;
	mkseg(1, 0, N-1);
	dfs1(X);

	//for(int i=1; i<=N; i++) printf("(%d %d %d)\n", dep[i], mxdep[i][0], mxdep[i][1]);
	
	//printf("[%d]\n", X);
	dfs2(X);

	Y=1;
	for(int i=1; i<=N; i++) if(dep[i]>dep[Y]) Y=i;
	for(int i=1; i<=N; i++) dep[i]=-1;
	dep[Y]=0;
	dfs1(Y);
	mkseg(1, 0, N-1);
	dfs2(Y);

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

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:90: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:91: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:92: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 5 ms 4992 KB Output is correct
2 Incorrect 9 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 321 ms 15864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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