oj.uz

Submission #376304

# Submission time Handle Problem Language Result Execution time Memory
376304 2021-03-11T08:04:00 Z dantoh000 Papričice (COCI20_papricice) C++14
110 / 110
 253 ms 30568 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> G[200005];
int p[200005];
int col[200005];
int sz[200005];
int root;
void dfs(int u){
    sz[u] = 1;
    for (auto v : G[u]){
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        sz[u] += sz[v];
    }
}
int findcentroid(int u){
    for (auto v : G[u]){
        if (v == p[u]) continue;
        if (sz[v] > n/2) return findcentroid(v);
    }
    return u;
}
vector<int> COL[200005];
set<int> rest;
set<int> hmm;
int curcol = 1;
void dfs2(int u){
    sz[u] = 1;
    COL[col[u]].push_back(u);
    for (auto v : G[u]){
        if (p[u] == v) continue;
        //printf("%d -> %d\n",u,v);
        p[v] = u;
        if (u == root){
            col[v] = curcol++;
        }
        else col[v] = col[u];
        dfs2(v);
        sz[u] += sz[v];
    }
}
int ans;
void process(int a, int b, int c){
    ans = min(ans, max(a,max(b,c)) - min(a,min(b,c)));
}
int main(){
    scanf("%d",&n);
    ans = n;
    for (int i = 0; i < n-1; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    p[1] = -1;
    dfs(1);
    root = findcentroid(1);
    for (int i = 1; i <= n; i++) p[i] = -1;
    col[root] = 0;
    dfs2(root);
    //printf("centroid is %d\n",root);
    for (int c = 1; c <= curcol; c++){
        for (auto u : COL[c]){
            //printf("col %d: %d\n",c,u);
        }
        for (auto u : COL[c]){
            hmm.insert(sz[u]);
        }
        for (auto u : COL[c]){
            int a = sz[u];
            int bad = n-a;
            ///search inside
            auto it = hmm.lower_bound(a+bad/2);
            if (it != hmm.end()){
                int b = *it - a;
                int c = n-a-b;
                process(a,b,c);
            }
            it = hmm.lower_bound(a+bad/2+1);
            if (it != hmm.end()){
                int b = *it - a;
                int c = n-a-b;
                process(a,b,c);
            }
            it = hmm.upper_bound(a+bad/2);
            if (it != hmm.begin()){
                it--;
                int b = *it - a;
                int c = n-a-b;
                process(a,b,c);
            }
            it = hmm.upper_bound(a+bad/2-1);
            if (it != hmm.begin()){
                it--;
                int b = *it - a;
                int c = n-a-b;
                process(a,b,c);
            }
            /// search outside
            it = rest.lower_bound(bad/2);
            if (it != rest.end()){
                int b = *it;
                int c = n-a-b;
                process(a,b,c);
            }
            it = rest.lower_bound(bad/2+1);
            if (it != rest.end()){
                int b = *it;
                int c = n-a-b;
                process(a,b,c);
            }
            it = rest.upper_bound(bad/2);
            if (it != rest.begin()){
                it--;
                int b = *it;
                int c = n-a-b;
                process(a,b,c);
            }
            it = rest.upper_bound(bad/2-1);
            if (it != rest.begin()){
                it--;
                int b = *it;
                int c = n-a-b;
                process(a,b,c);
            }
            //printf("after checking %d, ans = %d\n",u,ans);
        }
        for (auto u : COL[c]){
            rest.insert(sz[u]);
        }
        hmm.clear();
    }

    printf("%d",ans);
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:65:19: warning: unused variable 'u' [-Wunused-variable]
   65 |         for (auto u : COL[c]){
      |                   ^
papricice.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
papricice.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 8 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 8 ms 9836 KB Output is correct
7 Correct 8 ms 9836 KB Output is correct
8 Correct 8 ms 9836 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct
10 Correct 8 ms 9836 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 8 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 8 ms 9836 KB Output is correct
7 Correct 8 ms 9836 KB Output is correct
8 Correct 8 ms 9836 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct
10 Correct 8 ms 9836 KB Output is correct
11 Correct 240 ms 22192 KB Output is correct
12 Correct 253 ms 22128 KB Output is correct
13 Correct 188 ms 22284 KB Output is correct
14 Correct 210 ms 22436 KB Output is correct
15 Correct 244 ms 22120 KB Output is correct
16 Correct 150 ms 22888 KB Output is correct
17 Correct 207 ms 22312 KB Output is correct
18 Correct 238 ms 30568 KB Output is correct
19 Correct 237 ms 22376 KB Output is correct
20 Correct 243 ms 22120 KB Output is correct