oj.uz

Submission #366419

# Submission time Handle Problem Language Result Execution time Memory
366419 2021-02-14T07:19:55 Z NONAME Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 14572 KB 
#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.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 103 ms 5100 KB Output is correct
7 Correct 104 ms 5100 KB Output is correct
8 Correct 74 ms 5228 KB Output is correct
9 Correct 85 ms 5228 KB Output is correct
10 Correct 109 ms 5224 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 103 ms 5100 KB Output is correct
7 Correct 104 ms 5100 KB Output is correct
8 Correct 74 ms 5228 KB Output is correct
9 Correct 85 ms 5228 KB Output is correct
10 Correct 109 ms 5224 KB Output is correct
11 Execution timed out 1068 ms 14572 KB Time limit exceeded
12 Halted 0 ms 0 KB -