Submission #956037

#TimeUsernameProblemLanguageResultExecution timeMemory
956037vjudge1Papričice (COCI20_papricice)C++17
15 / 110
4 ms8236 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <cassert> using namespace std; using ll = long long; #define int ll #define fore(i, a, b) for(int i=a; i<b; ++i) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define pb(x) push_back(x) #define vi vector<int> const int N = 2e5+5; vi adj[N]; int n; /*int taken[N]; int dfs(int x, int prev=-1){ int tam = 1; for(int child : adj[x]){ if(child == prev) continue; tam += dfs(child, x); } if(taken[x]){ taken[x] = tam; tam = 0; } return tam; }*/ int tam[N]; int pa[N]; void dfs(int x, int prev=-1){ tam[x] = 1; pa[x] = prev; for(int child : adj[x]){ if(child == prev) continue; dfs(child, x); tam[x] += tam[child]; } } int f(int x, set<int> &A, set<int> &B, int pre=-1){ // A -> Es ancestro // B -> No es ancestro assert(B.count(tam[x])); B.erase(tam[x]); int res = 1e9; // primer caso if(A.lower_bound((n+tam[x])/2) != A.end()){ int p = *A.lower_bound((n + tam[x]) / 2); res = min(res, max({tam[x], p-tam[x], n-p}) - min({tam[x], p-tam[x], n-p})); } if(A.lower_bound((n + tam[x]) / 2) != A.begin()){ int p = *prev(A.lower_bound((n + tam[x])/2)); res = min(res, max({tam[x], p-tam[x], n-p}) - min({tam[x], p-tam[x], n-p})); } // segundo caso if(B.lower_bound((n - tam[x])/2) != B.end()){ int q = *B.lower_bound((n - tam[x]) / 2); res = min(res, max({tam[x], q, n-tam[x]-q}) - min({tam[x], q, n-tam[x]-q})); } if(B.lower_bound((n - tam[x])/2) != B.begin()){ int q = *prev(B.lower_bound((n - tam[x]) / 2)); res = min(res, max({tam[x], q, n-tam[x]-q}) - min({tam[x], q, n-tam[x]-q})); } A.insert(tam[x]); for(int child : adj[x]){ if(child == pre) continue; res = min(res, f(child, A, B, x)); assert(A.count(tam[x])); } A.erase(tam[x]); B.insert(tam[x]); return res; } // set<pair<int,int>> parientes; // void calcParientes(int start, int x, int prev=-1){ // if(start != x){ // parientes.insert(make_pair(min(start, x), max(start, x))); // } // for(int child : adj[x]){ // if(child == prev) continue; // calcParientes(start, child, x); // } // } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; /* if(n <= 200){ fore(i, 0, n-1){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } int ans = 1e9; taken[1] = 1; for(int i=2; i<=n; ++i){ for(int j=i+1; j<=n; ++j){ taken[1] = taken[i] = taken[j] = 1; dfs(1); ans = min(ans, max({taken[1],taken[i],taken[j]}) - min({taken[1],taken[i],taken[j]})); taken[1] = taken[i] = taken[j] = 0; } } cout << ans; return 0; } */ /* if(n <= 2000){ fore(i, 0, n-1){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } int ans = 1e9; dfs(1); fore(i, 1, n+1){ calcParientes(i, i, pa[i]); } fore(i, 2, n+1){ fore(j, i+1, n+1){ int p = i; int q = j; if(tam[p] > tam[q]) swap(p, q); int tam1 = tam[p]; int tam2 = tam[q]; if(parientes.count({min(p, q), max(p, q)})){ tam2 -= tam1; } int tam3 = n - tam1 - tam2; ans = min(ans, max({tam1, tam2, tam3}) - min({tam1, tam2, tam3})); } } cout << ans; return 0; } */ // complete task fore(i, 0, n-1){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1); set<int> A, B; fore(i, 2, n+1){ B.insert(tam[i]); } A.insert(tam[1]); int ans = 1e9; for(int child : adj[1]){ ans = min(ans, f(child, A, B, 1)); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...