oj.uz

Submission #864004

# Submission time Handle Problem Language Result Execution time Memory
864004 2023-10-21T16:39:16 Z MilosMilutinovic Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 20448 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],st[800005],dfn[200005],dfo[200005],T;
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]);
}

void build(int id,int l,int r){
	if(l==r) return (void)(st[id]=mn[l]);
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	st[id]=min(st[id<<1],st[id<<1|1]);
}

int query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return st[id];
	int mid=(l+r)/2;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return min(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}

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(1,1,n,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);
	build(1,1,n);
	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 4 ms 4704 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 4 ms 4708 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 5 ms 4704 KB Output is correct

Subtask #3
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 4 ms 4704 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 4 ms 4708 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 5 ms 4704 KB Output is correct
11 Execution timed out 1026 ms 20448 KB Time limit exceeded
12 Halted 0 ms 0 KB -