oj.uz

Submission #481209

# Submission time Handle Problem Language Result Execution time Memory
481209 2021-10-19T22:00:05 Z CSQ31 Papričice (COCI20_papricice) C++17
110 / 110
 276 ms 29252 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+1; 
int ans = 1e9,n;
vii adj(MAXN);
int sub[MAXN];
multiset<int>a,b;
void dfs0(int v,int u){
	sub[v] = 1;
	for(int x:adj[v]){
		if(x==u)continue;
		dfs0(x,v);
		sub[v]+=sub[x];
	}
}
void dfs(int v,int u){
	//sub[i] ,sub[j] and n-sub[i]-sub[j]
	//we want sub[j] and n-sub[i]-sub[j] to be as close as possible
	//sub[j] = n-sub[i]-sub[j]
	//sub[j] = n-sub[i]/2;
	auto it = a.lb((n-sub[v])/2);
	if(it != a.end())ans = min(ans,max({sub[v],*it,n-sub[v]-*it}) - min({sub[v],*it,n-sub[v]-*it}));
	if(it != a.begin()){
		it--;
		ans = min(ans,max({sub[v],*it,n-sub[v]-*it}) - min({sub[v],*it,n-sub[v]-*it}));
	}
	
	//ancestor
	//sub[i] , n-sub[j] , sub[j] - sub[i];
	//n - sub[j] = sub[j] - sub[i]
	//sub[j] = (n+sub[i])/2
	it = b.lb((n+sub[v])/2);
	if(it != b.end())ans = min(ans,max({sub[v],*it-sub[v],n-*it}) - min({sub[v],*it-sub[v],n-*it}));
	if(it != b.begin()){
	    it--;
	    ans = min(ans,max({sub[v],*it-sub[v],n-*it}) - min({sub[v],*it-sub[v],n-*it}));
    }
	
	b.insert(sub[v]);
	for(int x:adj[v]){
		if(x==u)continue;
		dfs(x,v);
	}
	b.erase(b.find(sub[v]));
	a.insert(sub[v]);
	
}
int main()
{
	owo
	cin>>n;
	for(int i=0;i<n-1;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	dfs0(1,0);
	dfs(1,0);
	cout<<ans;
	
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5092 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5092 KB Output is correct
11 Correct 238 ms 21644 KB Output is correct
12 Correct 248 ms 24004 KB Output is correct
13 Correct 206 ms 24412 KB Output is correct
14 Correct 220 ms 24224 KB Output is correct
15 Correct 276 ms 23936 KB Output is correct
16 Correct 158 ms 23980 KB Output is correct
17 Correct 221 ms 24124 KB Output is correct
18 Correct 236 ms 29252 KB Output is correct
19 Correct 214 ms 24088 KB Output is correct
20 Correct 263 ms 23988 KB Output is correct