Submission #1245538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245538		minhpk	Papričice (COCI20_papricice)	C++20	0 / 110	12 ms	23880 KiB

papricice

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
vector<int> z[1000005];
int sz[1000005];
int up[1000005];

void predfs(int i,int par){
     sz[i]=1;
     up[i]=par;
     for (auto p:z[i]){
          if (p==par){
              continue;
          }
          predfs(p,i);
          sz[i]+=sz[p];
     }
}
multiset <int> s1;
multiset <int> s2;
int min1=1e16;
int cal(int a,int b,int c){
    return max({a,b,c})-min({a,b,c});
}

void dfs(int i,int par){
     if (s1.empty() && s2.empty()){
     }else{
         auto it=s1.lower_bound((a+sz[i])/2);
         if (it!=s1.end()){
             min1=min(min1,cal(sz[i],*it-sz[i],a-sz[i]-(*it-sz[i])));
         }
         if (it!=s1.begin()){
             --it;
             min1=min(min1,cal(sz[i],*it-sz[i],a-sz[i]-(*it-sz[i])));
         }

         auto it1=s2.lower_bound((a-sz[i])/2);
         if (it1!=s2.end()){
             min1=min(min1,cal(sz[i],*it1-sz[i],a-sz[i]-(*it1-sz[i])));
         }
         if (it1!=s2.begin()){
             --it1;
             min1=min(min1,cal(sz[i],*it1-sz[i],a-sz[i]-(*it1-sz[i])));
         }

     }

     s1.insert(sz[i]);
     for (auto p:z[i]){
          if (p==par){
              continue;
          }
          dfs(p,i);

     }

         auto it1=s1.lower_bound(sz[i]);
         s2.insert(sz[i]);
         s1.erase(it1);

}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    predfs(1,0);
    dfs(1,0);
    cout << min1 << "\n";
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60