Submission #121253

#	Time	Username	Problem	Language	Result	Execution time	Memory
121253		imyujin	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	515 ms	19024 KiB

joi2019_ho_t5

#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||x>y) 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]-1));
	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]);
	return 0;
}

Compilation message (stderr)

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
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32