oj.uz

Submission #864013

# Submission time Handle Problem Language Result Execution time Memory
864013 2023-10-21T16:44:15 Z MilosMilutinovic Papričice (COCI20_papricice) C++14
110 / 110
 658 ms 33448 KB 
#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> 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]));
}

bool check(int d){
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4708 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 2 ms 4768 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4708 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 2 ms 4768 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 367 ms 23896 KB Output is correct
12 Correct 457 ms 26196 KB Output is correct
13 Correct 290 ms 26192 KB Output is correct
14 Correct 300 ms 26300 KB Output is correct
15 Correct 444 ms 26452 KB Output is correct
16 Correct 190 ms 25588 KB Output is correct
17 Correct 345 ms 26376 KB Output is correct
18 Correct 658 ms 33448 KB Output is correct
19 Correct 357 ms 26300 KB Output is correct
20 Correct 414 ms 26452 KB Output is correct