oj.uz

Submission #1047921

# Submission time Handle Problem Language Result Execution time Memory
1047921 2024-08-07T17:37:52 Z vjudge1 Papričice (COCI20_papricice) C++17
110 / 110
 120 ms 31312 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int oo = 1e9;
#define sz(a) (int)a.size()
#define eb emplace_back
using pii = pair<int, int>;
int n;
 
namespace arcv {
    int n;
    vector<int> adj[N];
    int par[N];
    int sz[N];
    int st[N];
    int en[N];
    int tour[N];
    int ans = oo;
    int times = 0;
    multiset<int> S;
 
    void calc_sz(int u, int p) {
        par[u] = p;
        sz[u] = 1;
 
        for(int v : adj[u]) {
            if(v == p)
                continue;
 
            calc_sz(v, u);
            sz[u] += sz[v];
        }
    }
 
    int get(int a, int b, int c) {
        return max({a, b, c}) - min({a, b, c});
    }
 
    void DFS1(int u, int p) {
        auto it = S.lower_bound((n - sz[u]) / 2);
 
        if(it != S.end())
            ans = min(ans, get(sz[u], *it, n - sz[u] - (*it)));
 
        if(it != S.begin())
            --it;
 
        if(it != S.end())
            ans = min(ans, get(sz[u], *it, n - sz[u] - (*it)));
 
        for(int v : adj[u]) {
            if(v == p)
                continue;
 
            DFS1(v, u);
        }
 
        S.emplace(sz[u]);
        en[u] = times;
    }
 
    void DFS2(int u, int p) {
        auto it = S.lower_bound((n + sz[u]) / 2);
 
        if(it != S.end())
            ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));
 
        if(it != S.begin())
            --it;
 
        if(it != S.end())
            ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));
 
        S.emplace(sz[u]);
 
        for(int v : adj[u]) {
            if(v == p)
                continue;
 
            DFS2(v, u);
        }
 
        S.erase(S.find(sz[u]));
    }
 
    void solution() {
        cin >> n;
 
        for(int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].eb(v);
            adj[v].eb(u);
        }
 
        calc_sz(1, 0);
        DFS1(1, 0);
        S.clear();
        DFS2(1, 0);
 
        cout << ans;
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    arcv::solution();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 1 ms 9052 KB Output is correct
9 Correct 1 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 1 ms 9052 KB Output is correct
9 Correct 1 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 95 ms 27088 KB Output is correct
12 Correct 105 ms 26932 KB Output is correct
13 Correct 77 ms 27476 KB Output is correct
14 Correct 87 ms 27260 KB Output is correct
15 Correct 113 ms 26932 KB Output is correct
16 Correct 79 ms 27084 KB Output is correct
17 Correct 120 ms 27220 KB Output is correct
18 Correct 114 ms 31312 KB Output is correct
19 Correct 94 ms 27220 KB Output is correct
20 Correct 118 ms 27012 KB Output is correct