Submission #316125

#	Time	Username	Problem	Language	Result	Execution time	Memory
316125		georgerapeanu	Papričice (COCI20_papricice)	C++11	50 / 110	1086 ms	40548 KiB

papricice

#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 (stderr)

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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60