oj.uz

Submission #388670

# Submission time Handle Problem Language Result Execution time Memory
388670 2021-04-12T14:26:49 Z phathnv Papričice (COCI20_papricice) C++11
110 / 110
 376 ms 28388 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Papricice"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2e5 + 1;

int n;
vector <int> adj[N];
int sz[N], res = N;
multiset <int> szPar, szChild;

void readInput(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void dfs1(int u, int p){
    sz[u] = 1;
    for(int v : adj[u]){
        if (v == p)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p){
    int best = (n - sz[u]) / 2;
    auto it = szChild.upper_bound(best);
    if (it != szChild.end()){
        int minSz = min(sz[u], min(*it, n - sz[u] - *it));
        int maxSz = max(sz[u], max(*it, n - sz[u] - *it));
        res = min(res, maxSz - minSz);
    }
    if (it != szChild.begin()){
        --it;
        int minSz = min(sz[u], min(*it, n - sz[u] - *it));
        int maxSz = max(sz[u], max(*it, n - sz[u] - *it));
        res = min(res, maxSz - minSz);
    }

    best += sz[u];
    it = szPar.upper_bound(best);
    if (it != szPar.end()){
        int minSz = min(sz[u], min(*it - sz[u], n - *it));
        int maxSz = max(sz[u], max(*it - sz[u], n - *it));
        res = min(res, maxSz - minSz);
    }
    if (it != szPar.begin()){
        --it;
        int minSz = min(sz[u], min(*it - sz[u], n - *it));
        int maxSz = max(sz[u], max(*it - sz[u], n - *it));
        res = min(res, maxSz - minSz);
    }

    szPar.insert(sz[u]);
    for(int v : adj[u]){
        if (v == p)
            continue;
        dfs2(v, u);
    }
    szChild.insert(sz[u]);
    szPar.erase(szPar.find(sz[u]));
}

void solve(){
    dfs1(1, -1);
    dfs2(1, -1);
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    solve();
    return 0;
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   87 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   88 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5152 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5144 KB Output is correct
9 Correct 5 ms 5144 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5152 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5144 KB Output is correct
9 Correct 5 ms 5144 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 332 ms 23972 KB Output is correct
12 Correct 350 ms 24008 KB Output is correct
13 Correct 295 ms 24548 KB Output is correct
14 Correct 338 ms 24196 KB Output is correct
15 Correct 376 ms 24196 KB Output is correct
16 Correct 278 ms 23932 KB Output is correct
17 Correct 348 ms 24120 KB Output is correct
18 Correct 344 ms 28388 KB Output is correct
19 Correct 317 ms 24156 KB Output is correct
20 Correct 354 ms 24028 KB Output is correct