oj.uz

Submission #316129

# Submission time Handle Problem Language Result Execution time Memory
316129 2020-10-25T11:07:41 Z georgerapeanu Papričice (COCI20_papricice) C++11
110 / 110
 280 ms 20856 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

int n;
vector<int> graph[NMAX + 5];

int w[NMAX + 5];

void predfs(int nod,int tata) {
    w[nod] = 1;
    for(auto it:graph[nod]) {
        if(it != tata) {
            predfs(it,nod);
            w[nod] += w[it];
        }
    }
}

inline void add(map<int,int> &s,int val){
    s[val]++;
}

inline void rem(map<int,int> &s,int val){
    s[val]--;
    if(s[val] == 0){
        s.erase(val);
    }
}

int compute(int a,int b,int c) {
    return max(max(a,b),c) - min(min(a,b),c);
}

int ans = 1e9;
map<int,int> a,b;

void dfs(int nod,int tata) {

    if(tata != 0){
        map<int,int> :: iterator it;
        it = b.lower_bound((n - w[nod]) / 2);
        if(it != b.end()){
            ans = min(ans,compute(w[nod],n - w[nod] - it->first,it->first));
        }
        if(it != b.begin()){
            it--;
            ans = min(ans,compute(w[nod],n - w[nod] - it->first,it->first));
        }
        
        it = a.lower_bound((n + w[nod]) / 2);
        if(it != a.end()){
            ans = min(ans,compute(w[nod],n - it->first,it->first - w[nod]));
        }
        if(it != a.begin()){
            it--;
            ans = min(ans,compute(w[nod],n - it->first,it->first - w[nod]));
        }
    }

    add(a,w[nod]);

    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        dfs(it,nod);
    }

    rem(a,w[nod]);
    add(b,w[nod]);
}

int main() {

    scanf("%d",&n);

    for(int i = 1; i < n; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    predfs(1,0);
    dfs(1,0);

    printf("%d\n",ans);

    return 0;
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
papricice.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 5028 KB Output is correct
9 Correct 5 ms 5152 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 5028 KB Output is correct
9 Correct 5 ms 5152 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct
11 Correct 255 ms 12408 KB Output is correct
12 Correct 280 ms 12408 KB Output is correct
13 Correct 210 ms 12792 KB Output is correct
14 Correct 249 ms 12664 KB Output is correct
15 Correct 280 ms 12280 KB Output is correct
16 Correct 173 ms 12916 KB Output is correct
17 Correct 239 ms 12408 KB Output is correct
18 Correct 273 ms 20856 KB Output is correct
19 Correct 230 ms 12536 KB Output is correct
20 Correct 250 ms 12280 KB Output is correct