Submission #316128

#TimeUsernameProblemLanguageResultExecution timeMemory
316128georgerapeanuPapričice (COCI20_papricice)C++11
50 / 110
1090 ms22136 KiB
#include <bits/stdc++.h> using namespace std; const int NMAX = 2e5; int n; vector<int> graph[NMAX + 5]; vector<map<int,int> > sets; int w[NMAX + 5]; map<int,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]; } } } inline void add(map<int,int> &s,int val){ s[val]++; } inline void rem(map<int,int> &s,int val){ s[val]--; if(s[val] == 0){ s.erase(val); } } void dfs2(int nod,int tata,int t,map<int,int> &s) { if(t == 1) { add(s,w[nod]); } else { rem(s,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; map<int,int> :: iterator it; for(auto s:sets) { it = s.lower_bound(target_val); if(it == s.end() || it->first == n - w[nod]) { ; } else { ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first)); } if(it == s.begin()) { continue; } it--; if(it->first == n - w[nod]) { ; } else { ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first)); } } } 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) { add(sets[0],n - w[bigChild]); dfs(bigChild,nod); sets.push_back(map<int,int>()); sets.back().swap(down[bigChild]); rem(sets[0],n - w[bigChild]); } for(auto it:graph[nod]) { if(it == tata || it == bigChild) { continue; } dfs2(it,nod,-1,sets[0]); add(sets[0],n - w[it]); dfs(it,nod); rem(sets[0],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(map<int,int>()); predfs(1,0); dfs(1,0); printf("%d\n",ans); return 0; }

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
papricice.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...