oj.uz

Submission #448168

# Submission time Handle Problem Language Result Execution time Memory
448168 2021-07-29T05:04:15 Z jk410 Papričice (COCI20_papricice) C++17
50 / 110
 90 ms 588 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int N,Ans=INF;
int Size[2001];
vector<int> Edge[2001];
vector<pair<int,int>> Edge_List;
void dfs(int v,int par){
    Size[v]=1;
    for (int i:Edge[v]){
        if (i==par)
            continue;
        dfs(i,v);
        Size[v]+=Size[i];
    }
}
void f(int v,int par){
    for (int i=1; i<=N; i++)
        Size[i]=0;
    dfs(v,par);
    for (int i=1; i<=N; i++){
        if (!Size[i]||i==par)
            continue;
        Ans=min(Ans,max({Size[i],Size[v]-Size[i],N-Size[v]})-min({Size[i],Size[v]-Size[i],N-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);
        Edge_List.push_back({a,b});
    }
    for (auto i:Edge_List){
        f(i.first,i.second);
        f(i.second,i.first);
    }
    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 84 ms 448 KB Output is correct
7 Correct 89 ms 452 KB Output is correct
8 Correct 76 ms 460 KB Output is correct
9 Correct 75 ms 460 KB Output is correct
10 Correct 90 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 84 ms 448 KB Output is correct
7 Correct 89 ms 452 KB Output is correct
8 Correct 76 ms 460 KB Output is correct
9 Correct 75 ms 460 KB Output is correct
10 Correct 90 ms 460 KB Output is correct
11 Runtime error 1 ms 588 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -