제출 #864008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864008		MilosMilutinovic	Papričice (COCI20_papricice)	C++14	50 / 110	1050 ms	33108 KiB

papricice

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,v[400005],nxt[400005],h[200005],tot,sz[200005],mn[200005],dfn[200005],dfo[200005],T,lg[200005],st[200005][20];
multiset<int> s1,s2;
bool ok;

void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}

void dfs1(int x,int fa){
	dfn[x]=++T;
	sz[x]=1;
	for(int p=h[x];p;p=nxt[p]){
		if(v[p]!=fa){
			dfs1(v[p],x);
			sz[x]+=sz[v[p]];
		}
	}
	dfo[x]=T;
	mn[sz[x]]=min(mn[sz[x]],dfo[x]);
}

int query(int l,int r){
	int k=lg[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}

void dfs2(int x,int fa,int d){
	/*
		//sz[x]-d<=n-t<=sz[x]+d
		//n-sz[x]-d<=t<=n-sz[x]+d

		//sz[x]-d<=t-sz[x]<=sz[x]+d
		//2*sz[x]-d<=t<=2*sz[x]+d

		//n-t-d<=t-sz[x]<=n-t+d
		//n-d+sz[x]<=2*t<=n+d+sz[x]



		//sz[x]-d<=t<=sz[x]+d

		//2*sz[x]-d<=n-t-sz[x]<=sz[x]+d
		//n-d-2*sz[x]<=t<=n+d-2*sz[x]

		//n-sz[x]-d<=2*t<=n-sz[x]+d
	*/
	int L=max({n-sz[x]-d,2*sz[x]-d,(n-d+sz[x]+1)/2});
	int R=min({n-sz[x]+d,2*sz[x]+d,(n+d+sz[x])/2});
	auto it=s2.lower_bound(L);
	if(it!=s2.end()&&*it<=R) ok=true;
	s2.insert(sz[x]);
	L=max({sz[x]-d,n-d-2*sz[x],(n-sz[x]-d+1)/2});
	R=min({sz[x]+d,n+d-2*sz[x],(n-sz[x]+d)/2});
	L=max(1,L); R=min(R,n);
	if(L<=R&&query(L,R)<dfn[x]) ok=true;
	for(int p=h[x];p;p=nxt[p]){
		if(v[p]!=fa){
			dfs2(v[p],x,d);
		}
	}
	s2.erase(s2.find(sz[x]));
	s1.insert(sz[x]);
}

bool check(int d){
	s1.clear();
	s2.clear();
	ok=false;
	dfs2(1,1,d);
	return ok;	
}

int main(){
	n=readint();
	for(int i=1;i<n;i++) addedge(readint(),readint());
	for(int i=1;i<=n;i++) mn[i]=1e9;
	dfs1(1,1);
	for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++) st[i][0]=mn[i];
	for(int j=1;j<20;j++){
		for(int i=1;i+(1<<j)<=n+1;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	int l=0,r=n,ans=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60