Submission #448175

#	Time	Username	Problem	Language	Result	Execution time	Memory
448175		jk410	Papričice (COCI20_papricice)	C++17	110 / 110	279 ms	28352 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int N,Ans=INF;
int Size[200001];
vector<int> Edge[200001];
multiset<int> Par,NotInSubTree;
int get_size(int v,int par){
    Size[v]=1;
    for(int i:Edge[v]){
        if (i==par)
            continue;
        Size[v]+=get_size(i,v);
    }
    return Size[v];
}
int f(int a,int b,int c){
    return max({a,b,c})-min({a,b,c});
}
void dfs(int v,int par){
    auto it=NotInSubTree.lower_bound((N-Size[v])/2);
    if (it!=NotInSubTree.end())
        Ans=min(Ans,f(Size[v],*it,N-Size[v]-(*it)));
    if (it!=NotInSubTree.begin()){
        it--;
        Ans=min(Ans,f(Size[v],*it,N-Size[v]-(*it)));
    }
    it=Par.lower_bound((N+Size[v])/2);
    if (it!=Par.end())
        Ans=min(Ans,f(Size[v],*it-Size[v],N-(*it)));
    if (it!=Par.begin()){
        it--;
        Ans=min(Ans,f(Size[v],*it-Size[v],N-(*it)));
    }
    Par.insert(Size[v]);
    for (int i:Edge[v]){
        if (i==par)
            continue;
        dfs(i,v);
    }
    Par.erase(Par.find(Size[v]));
    NotInSubTree.insert(Size[v]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    for (int i=1; i<N; i++){
        int a,b;
        cin>>a>>b;
        Edge[a].push_back(b);
        Edge[b].push_back(a);
    }
    get_size(1,0);
    dfs(1,0);
    cout<<Ans;
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60