Submission #480337

#	Time	Username	Problem	Language	Result	Execution time	Memory
480337		lukameladze	Papričice (COCI20_papricice)	C++14	110 / 110	512 ms	41776 KiB

papricice

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int n,sz[N],ans,rem,szz,a,b;
multiset <int> ms,mss,ms1,mss1;
multiset <int> :: iterator it;
vector <int> v[N];
int get(int a, int b, int c) {
     return (max(a,max(b,c))- min(a,min(b,c)));
}
void dfs(int a, int p) {
     sz[a] = 1;
     for (int i = 0; i < v[a].size(); i++) {
          if (v[a][i] == p) continue;
          dfs(v[a][i],a);
          sz[a] += sz[v[a][i]];
     }
}
void dfs1(int a, int p) {
    // cout<<a<<" "<<(int)ms.size()<<" "<<ms1.size()<<endl;
     rem = (n - sz[a]);
     it = ms.lower_bound(rem/2);
     if (it != ms.end()) {
          ans = min(ans, get(sz[a],*it, n - sz[a] - *it));
     }
     it = mss.lower_bound(-rem/2);
     if (it != mss.end()) {
          ans = min(ans, get(sz[a], -(*it), n - sz[a] - (-(*it))));
     }
     it = ms1.lower_bound(rem/2 + sz[a]);
     if (it != ms1.end()) {
          ans = min(ans, get(sz[a], (*it)-sz[a], n - (*it)));
     }
     it = mss1.lower_bound(-(rem/2+sz[a]));
     szz = -(*it);
     if (it != mss1.end()) {
          ans = min(ans, get(sz[a], szz - sz[a], n - szz));
     }
     ms1.insert(sz[a]);
     mss1.insert(-sz[a]);
     for (int i = 0; i < v[a].size(); i++) {
          if (v[a][i] == p) continue;
          dfs1(v[a][i],a);
     }
     ms.insert(sz[a]);
     mss.insert(-sz[a]);
     ms1.erase(ms1.find(sz[a]));
     mss1.erase(mss1.find(-sz[a]));
}
main() {
     cin>>n;
     for (int i = 1; i <= n - 1; i++) {
          cin>>a>>b;
          v[a].pb(b);
          v[b].pb(a);
     } ans = 1e9;
     dfs(1,0);
     dfs1(1,0);
    
     cout<<ans<<endl;
}

Compilation message (stderr)

papricice.cpp: In function 'void dfs(int, int)':
papricice.cpp:16:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |      for (int i = 0; i < v[a].size(); i++) {
      |                      ~~^~~~~~~~~~~~~
papricice.cpp: In function 'void dfs1(int, int)':
papricice.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |      for (int i = 0; i < v[a].size(); i++) {
      |                      ~~^~~~~~~~~~~~~
papricice.cpp: At global scope:
papricice.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main() {
      | ^~~~

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