Submission #334729

#TimeUsernameProblemLanguageResultExecution timeMemory
334729achibasadzishviliPapričice (COCI20_papricice)C++14
0 / 110
9 ms12140 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll ch[500005],dp[500005],ans,n; vector<ll>v[500005]; void go(ll x,ll par){ ch[x] = 1; dp[x] = 0; for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ go(v[x][i] , x); ch[x] += ch[v[x][i]]; dp[x] = max(dp[x] , dp[v[x][i]]); } } for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ dp[x] = max(dp[x] , min(ch[v[x][i]] , ch[x] - ch[v[x][i]])); } } ll mn = min(dp[x] , n - ch[x]); ll mx = max(ch[x] - dp[x] , n - ch[x]); ans = min(ans , mx - mn); } void ze(ll x,ll par,ll zed){ ll mn = min(zed , ch[x]); ll mx = max(n - ch[x] - zed , ch[x]); ans = min(ans , mx - mn); multiset<ll>st,st1; st.insert(zed); for(int i=0; i<v[x].size(); i++){ if(v[x][i] == par)continue; st.insert(dp[v[x][i]]); } for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ ll Z = zed; for(int j=0; j<v[x].size(); j++){ if(v[x][j] != par && i != j){ Z = max(Z , dp[v[x][j]]); Z = max(Z , min(n - ch[v[x][i]] - ch[v[x][j]] , ch[v[x][j]])); } } //st.erase(st.find(ch[v[x][i]])); //st.erase(st.find(dp[v[x][i]])); ze(v[x][i] , x , Z); //st.insert(ch[v[x][i]]); //st.insert(dp[v[x][i]]); } } } int main(){ ios::sync_with_stdio(false); cin >> n; for(int i=1; i<n; i++){ ll x,y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } ans = n; go(1 , 0); ze(1 , 0 , 0); cout << ans << '\n'; return 0; }

Compilation message (stderr)

papricice.cpp: In function 'void go(long long int, long long int)':
papricice.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
papricice.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
papricice.cpp: In function 'void ze(long long int, long long int, long long int)':
papricice.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
papricice.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
papricice.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int j=0; j<v[x].size(); j++){
      |                          ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...