제출 #955988

#제출 시각아이디문제언어결과실행 시간메모리
955988shezittPapričice (COCI20_papricice)C++17
50 / 110
63 ms6748 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> 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 = 2005; 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]; } } 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...