oj.uz

Submission #448174

# Submission time Handle Problem Language Result Execution time Memory
448174 2021-07-29T06:05:39 Z jk410 Papričice (COCI20_papricice) C++17
50 / 110
 3 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int N,Ans=INF;
int Size[2001];
vector<int> Edge[2001];
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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Runtime error 1 ms 460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -