oj.uz

Submission #316125

# Submission time Handle Problem Language Result Execution time Memory
316125 2020-10-25T10:51:19 Z georgerapeanu Papričice (COCI20_papricice) C++11
50 / 110
 1000 ms 40548 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

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

vector<multiset<int> > sets;

int w[NMAX + 5];
multiset<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];
        }
    }
}

void dfs2(int nod,int tata,int t,multiset<int> &s){
    if(t == 1){
        s.insert(w[nod]);
    }
    else{
        s.erase(s.find(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;

        multiset<int> :: iterator it;

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

    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){
        sets[0].insert(n - w[bigChild]);
        dfs(bigChild,nod);
        sets.push_back(multiset<int>());
        sets.back().swap(down[bigChild]);
        sets[0].erase(sets[0].find(n - w[bigChild]));
    }

    for(auto it:graph[nod]){
        if(it == tata || it == bigChild){
            continue;
        }
        dfs2(it,nod,-1,sets[0]);
        sets[0].insert(n - w[it]);
        dfs(it,nod);
        sets[0].erase(sets[0].find(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(multiset<int>());

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

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

    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 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 12 ms 14464 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 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 12 ms 14464 KB Output is correct
6 Correct 196 ms 14968 KB Output is correct
7 Correct 199 ms 14840 KB Output is correct
8 Correct 198 ms 14840 KB Output is correct
9 Correct 202 ms 14968 KB Output is correct
10 Correct 198 ms 14840 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 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 12 ms 14464 KB Output is correct
6 Correct 196 ms 14968 KB Output is correct
7 Correct 199 ms 14840 KB Output is correct
8 Correct 198 ms 14840 KB Output is correct
9 Correct 202 ms 14968 KB Output is correct
10 Correct 198 ms 14840 KB Output is correct
11 Execution timed out 1086 ms 40548 KB Time limit exceeded
12 Halted 0 ms 0 KB -