Submission #366419

#	Time	Username	Problem	Language	Result	Execution time	Memory
366419		NONAME	Papričice (COCI20_papricice)	C++14	50 / 110	1068 ms	14572 KiB

papricice

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
using namespace std;

const int man = (int)(2e5 + 500);   

int n, ans, timer;
int sz[man], tin[man], tout[man];
vector <int> g[man];

void dfs(int v, int pr) {
    tin[v] = timer++;
    sz[v] = 1;
    for (int& u : g[v]) {
        if (u == pr) {
            continue;
        }
        dfs(u, v);
        sz[v] += sz[u];
    }
    tout[v] = timer++;
}

bool upper(int v, int u) {
    return (tin[v] <= tin[u]) && (tout[v] >= tout[u]);
}

void upd(int v, int u, int fx, int f1) {
    int f2, f3;
    if (upper(u, fx) == true) {
        f2 = sz[u] - sz[fx];
        f3 = n - sz[u];
    } else {
        f2 = sz[u];
        f3 = n - sz[u] - sz[fx];
    }

    if (ans == -1) {
        ans = max(max(f1, f2), f3) - min(min(f1, f2), f3);
    } else {
        ans = min(ans, max(max(f1, f2), f3) - min(min(f1, f2), f3));
    }
}

void rec(int v, int pr, int mk, int cur) {
    for (auto& u : g[v]) {
        if ((u == pr) || (u == mk)) {
            continue;
        }
        rec(u, v, mk, cur);

        upd(v, u, mk, cur);
    }
}

void calc(int v, int pr) {
    for (auto& u : g[v]) {
        if (u == pr) {
            continue;
        }

        rec(0, -1, u, sz[u]);
        calc(u, v);
    }
}

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

    #ifdef _LOCAL
        in("inD.txt");
        out("outD.txt");
    #endif

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;

        g[v].push_back(u);
        g[u].push_back(v);
    }

    dfs(0, -1);

    ans = -1;
    calc(0, -1);

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60