Submission #334720

#TimeUsernameProblemLanguageResultExecution timeMemory
334720achibasadzishviliPaprič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); } 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); 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++){
      |                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...