oj.uz

답안 #448175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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