oj.uz

Submission #376262

# Submission time Handle Problem Language Result Execution time Memory
376262 2021-03-11T06:32:36 Z lyc Papričice (COCI20_papricice) C++14
0 / 110
 8 ms 10476 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 = 2e5+5;

int N;
vector<int> al[mxN];

namespace cd {
    int fa[mxN], sub[mxN];
    vector<int> tree[mxN];

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

    int getc(int u, int p, int sz) {
        for (int& v : al[u]) if (v != p && fa[v] == -1 && sub[v] > sz/2) {
            return getc(v,u,sz);
        }
        return u;
    }

    int decomp(int u, int p) {
        int c = getc(u, -1, dfs(u,-1));
        fa[c] = p;
        for (int& v : al[c]) if (fa[v] == -1) {
            tree[c].push_back(decomp(v, c));
        }
        return c;
    }

    void run(int rt) {
        memset(fa,-1,sizeof fa);
        decomp(rt,0);
    }



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

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

    int solve(int rt) {
        dfs2(rt, -1);

        int ans = mxN;
        FOR(i,1,N){
            FOR(j,i+1,N){
                int c = 0;

                for (int x = i; x != -1; x = fa[x]) {
                    if (x == j) {
                        c = 1;
                        break;
                    }
                }

                for (int x = j; x != -1; x = fa[x]) {
                    if (x == i) {
                        c = 2;
                        break;
                    }
                }

                if (c == 0) 
                    ans = min(ans, calc(sub[i],sub[j],N-sub[i]-sub[j]));
                else if (c == 1)
                    ans = min(ans, calc(sub[i],sub[j]-sub[i],N-sub[j]));
                else
                    ans = min(ans, calc(sub[i]-sub[j],sub[j],N-sub[i]));
            }
        }
        return ans;
    }
}

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);
    }

    cd::run(1);
    cout << cd::solve(1) << '\n';
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10476 KB Output isn't correct
2 Halted 0 ms 0 KB -