oj.uz

Submission #316128

# Submission time Handle Problem Language Result Execution time Memory
316128 2020-10-25T11:01:47 Z georgerapeanu Papričice (COCI20_papricice) C++11
50 / 110
 1000 ms 22136 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

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

vector<map<int,int> > sets;

int w[NMAX + 5];
map<int,int> down[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);
    }
}

void dfs2(int nod,int tata,int t,map<int,int> &s) {
    if(t == 1) {
        add(s,w[nod]);
    }
    else {
        rem(s,w[nod]);
    }

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

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

int ans = 1e9;

void dfs(int nod,int tata) {

    if(tata != 0) {
        int target_val = (n - w[nod]) / 2;

        map<int,int> :: iterator it;

        for(auto s:sets) {
            it = s.lower_bound(target_val);
            if(it == s.end() || it->first == n - w[nod]) {
                ;
            }
            else {
                ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first));
            }
            if(it == s.begin()) {
                continue;
            }
            it--;
            if(it->first == n - w[nod]) {
                ;
            }
            else {
                ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first));
            }
        }
    }

    int bigChild =-1;
    for(auto it:graph[nod]) {
        if(it == tata) {
            continue;
        }
        if(bigChild == -1 || w[it] > w[bigChild]) {
            bigChild = it;
        }
    }

    for(auto it:graph[nod]) {
        if(it == tata || it == bigChild) {
            continue;
        }
        dfs2(it,nod,1,sets[0]);
    }

    if(bigChild != -1) {
        add(sets[0],n - w[bigChild]);
        dfs(bigChild,nod);
        sets.push_back(map<int,int>());
        sets.back().swap(down[bigChild]);
        rem(sets[0],n - w[bigChild]);
    }

    for(auto it:graph[nod]) {
        if(it == tata || it == bigChild) {
            continue;
        }
        dfs2(it,nod,-1,sets[0]);
        add(sets[0],n - w[it]);
        dfs(it,nod);
        rem(sets[0],n - w[it]);
        dfs2(it,nod,1,sets[0]);
    }

    if(bigChild != -1) {
        down[nod].swap(sets.back());
        sets.pop_back();
    }

    for(auto it:graph[nod]) {
        if(it == tata || it == bigChild) {
            continue;
        }
        dfs2(it,nod,-1,sets[0]);
        dfs2(it,nod,1,down[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);
    }

    sets.push_back(map<int,int>());

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

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

    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 21 ms 14464 KB Output is correct
7 Correct 36 ms 14592 KB Output is correct
8 Correct 18 ms 14464 KB Output is correct
9 Correct 19 ms 14464 KB Output is correct
10 Correct 30 ms 14584 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 21 ms 14464 KB Output is correct
7 Correct 36 ms 14592 KB Output is correct
8 Correct 18 ms 14464 KB Output is correct
9 Correct 19 ms 14464 KB Output is correct
10 Correct 30 ms 14584 KB Output is correct
11 Execution timed out 1090 ms 22136 KB Time limit exceeded
12 Halted 0 ms 0 KB -