oj.uz

Submission #448175

# Submission time Handle Problem Language Result Execution time Memory
448175 2021-07-29T06:11:08 Z jk410 Papričice (COCI20_papricice) C++17
110 / 110
 279 ms 28352 KB 
#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.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 5016 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 5016 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 5152 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 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 5016 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 5152 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 266 ms 23968 KB Output is correct
12 Correct 271 ms 23992 KB Output is correct
13 Correct 210 ms 24488 KB Output is correct
14 Correct 233 ms 24132 KB Output is correct
15 Correct 264 ms 24004 KB Output is correct
16 Correct 194 ms 23920 KB Output is correct
17 Correct 248 ms 24004 KB Output is correct
18 Correct 264 ms 28352 KB Output is correct
19 Correct 238 ms 24172 KB Output is correct
20 Correct 279 ms 24012 KB Output is correct