oj.uz

Submission #880170

# Submission time Handle Problem Language Result Execution time Memory
880170 2023-11-28T23:05:22 Z Ahmed_Solyman Papričice (COCI20_papricice) C++14
110 / 110
 183 ms 27828 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
const int N=2e5+5;
vector<int>adj[N];
int n,subtree[N];
int dfs(int node,int parent){
    subtree[node]=1;
    for(auto i:adj[node]){
        if(i!=parent){
            subtree[node]+=dfs(i,node);
        }
    }
    return subtree[node];
}
int ans=N;
set<int> solve1(int node,int p){ /// for those whose lca is one of the,
    set<int>s;
    for(auto i:adj[node]){
        if(i!=p){
            set<int>u=solve1(i,node);
            if(u.size()>s.size())swap(u,s);
            for(auto p:u)s.insert(p);
        }
    }
    // n-subtree[node] , subtree[node]-subtree[ch] , subtree[ch]
    auto iter=s.lower_bound(subtree[node]>>1);
    if(iter!=s.end()){
        int ch=*iter;
        ans=min(ans,max({n-subtree[node],subtree[node]-ch,ch})-min({n-subtree[node],subtree[node]-ch,ch}));
    }
    if(iter!=s.begin()){
        int ch=*(--iter);
        ans=min(ans,max({n-subtree[node],subtree[node]-ch,ch})-min({n-subtree[node],subtree[node]-ch,ch}));
    }
    s.insert(subtree[node]);
    return s;
}
set<int>s;
void solve2(int node,int p){ // others
    if(s.size()){
        int x=n-subtree[node];
        auto iter=s.lower_bound(x>>1);
        if(iter!=s.end()){
            int ch=*iter;
            ans=min(ans,max({n-subtree[node]-ch,ch,subtree[node]})-min({n-subtree[node]-ch,ch,subtree[node]}));
        }
        if(iter!=s.begin()){
            int ch=*(--iter);
            ans=min(ans,max({n-subtree[node]-ch,ch,subtree[node]})-min({n-subtree[node]-ch,ch,subtree[node]}));
        }
    }
    for(auto i:adj[node]){
        if(i!=p){
            solve2(i,node);
        }
    }
    s.insert(subtree[node]);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    #endif
    fast
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    solve1(1,1);
    solve2(1,1);
    cout<<ans<<endl;
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5544 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 94 ms 12380 KB Output is correct
12 Correct 183 ms 15052 KB Output is correct
13 Correct 73 ms 15164 KB Output is correct
14 Correct 90 ms 15020 KB Output is correct
15 Correct 101 ms 14672 KB Output is correct
16 Correct 71 ms 14924 KB Output is correct
17 Correct 95 ms 14936 KB Output is correct
18 Correct 114 ms 27828 KB Output is correct
19 Correct 139 ms 14816 KB Output is correct
20 Correct 141 ms 14928 KB Output is correct