oj.uz

Submission #376312

# Submission time Handle Problem Language Result Execution time Memory
376312 2021-03-11T08:15:50 Z lyc Papričice (COCI20_papricice) C++14
50 / 110
 16 ms 4460 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 2005;

int N;
vector<int> al[mxN];
int sub[mxN], pa[mxN];
bool isp[mxN][mxN];

int dfs(int u, int p) {
    sub[u] = 1;
    pa[u] = p;
    for (int& v : al[u]) if (v != p) {
        sub[u] += dfs(v,u);
    }
    return sub[u];
}

inline int calc(int a, int b, int c) {
    return max({a,b,c})-min({a,b,c});
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int X, Y; cin >> X >> Y;
        al[X].push_back(Y);
        al[Y].push_back(X);
    }

    dfs(1,-1);

    FOR(i,1,N){
        for (int j = pa[i]; j != -1; j = pa[j]) isp[i][j] = 1;
    }

    int ans = mxN;
    FOR(i,1,N){
        FOR(j,i+1,N){
            if (isp[i][j])
                ans = min(ans, calc(sub[i],sub[j]-sub[i],N-sub[j]));
            else if (isp[j][i])
                ans = min(ans, calc(sub[j],sub[i]-sub[j],N-sub[i]));
            else
                ans = min(ans, calc(sub[i],sub[j],N-sub[i]-sub[j]));
        }
    }
    cout << ans << '\n';
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 10 ms 4332 KB Output is correct
7 Correct 16 ms 4460 KB Output is correct
8 Correct 11 ms 4332 KB Output is correct
9 Correct 11 ms 4332 KB Output is correct
10 Correct 11 ms 4332 KB Output is correct

Subtask #3
0 / 60.0

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