oj.uz

Submission #479553

# Submission time Handle Problem Language Result Execution time Memory
479553 2021-10-12T06:30:50 Z kakayoshi Papričice (COCI20_papricice) C++14
110 / 110
 217 ms 21444 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,0};
const ll maxN=2e5+5;
int n,sum[maxN],ans;
set<int> a,b;
vector <int> check[maxN];
int build(int u, int father) // build subtree
{
    sum[u]=1;
    for(int v:check[u])
    if (v!=father)
        sum[u]+=build(v,u);
    return sum[u];
}
void dfs(int u, int father)
{
    // set A: save current ancestors of u
    // set B: save others
    // case 1: v is an ancestor of u
    // => | (sum[v] - sum[u]) - (n-sum[v]) |  : is as small as possible
    // => | sum[v] - (n+sum[u])/2 |
    int x=(n+sum[u])/2;
    auto it=a.lower_bound(x);
    if (it!=a.end())
        ans=min(ans,max(sum[u],max(n-(*it),(*it)-sum[u]))-min(sum[u],min(n-(*it),(*it)-sum[u])));
    if (it!=a.begin())
    {
        it--;
        ans=min(ans,max(sum[u],max(n-(*it),(*it)-sum[u]))-min(sum[u],min(n-(*it),(*it)-sum[u])));
    }
    // case 2: v is not an ancestor of u
    // => | (n- sum[u] - sum[v]) - sum[v] |
    // => | (n-sum[u])/2 - sum[v] |
    x=(n-sum[u])/2;
    it=b.lower_bound(x);
    if (it!=b.end())
        ans=min(ans,max(sum[u],max(n-(*it)-sum[u],(*it)))-min(sum[u],min(n-(*it)-sum[u],(*it))));
    if (it!=b.begin())
    {
        it--;
        ans=min(ans,max(sum[u],max(n-(*it)-sum[u],(*it)))-min(sum[u],min(n-(*it)-sum[u],(*it))));
    }
    a.insert(sum[u]);
    for(int v:check[u])
    if (v!=father)
        dfs(v,u);
    a.erase(sum[u]);
    b.insert(sum[u]);
    return;
}
void solve()
{
    cin>>n;
    forw(i,1,n-1)
    {
        int u,v;
        cin>>u>>v;
        check[u].pb(v);
        check[v].pb(u);
    }
    int s=0;
    forw(i,1,n)
    if (check[i].size()==1)
    {
        s=i;
        break;
    }
    ans=1e9;
    build(s,0);
    //cout<<"finish"<<endl;
    dfs(s,0);
    cout<<ans;
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    return 0;
}

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 5012 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 5012 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5020 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 5012 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5020 KB Output is correct
11 Correct 196 ms 12288 KB Output is correct
12 Correct 207 ms 14516 KB Output is correct
13 Correct 175 ms 15076 KB Output is correct
14 Correct 186 ms 14812 KB Output is correct
15 Correct 199 ms 14448 KB Output is correct
16 Correct 134 ms 14508 KB Output is correct
17 Correct 180 ms 14584 KB Output is correct
18 Correct 217 ms 21444 KB Output is correct
19 Correct 167 ms 14724 KB Output is correct
20 Correct 213 ms 14532 KB Output is correct