Submission #460716

#TimeUsernameProblemLanguageResultExecution timeMemory
460716benson0402Papričice (COCI20_papricice)C++14
50 / 110
123 ms588 KiB
#pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; #define F first #define S second #define ALL(x) x.begin(), x.end() #define MEM(x) memset(x, 0, sizeof(x)) #define MEMS(x) memset(x, -1, sizeof(x)) #define eb emplace_back #define ep emplace #define mkp make_pair const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; /*------------------------------------------------------------------*/ const int N = 2000 + 5; vector<int> G[N]; vector<pii> edge; int sz[N]; void dfs(int u, int p) { sz[u] = 1; for(auto& v : G[u]) if(v != p) { dfs(v, u); sz[u] += sz[v]; } } inline void solve() { int n; cin >> n; for(int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; G[u].eb(v); G[v].eb(u); edge.eb(u, v); } int ans = N; for(auto& x : edge) { MEM(sz); dfs(x.F, x.S); for(int i = 0; i < n; ++i) { int mx = max({n - sz[x.F], sz[x.F] - sz[i], sz[i]}); int mn = min({n - sz[x.F], sz[x.F] - sz[i], sz[i]}); ans = min(ans, mx - mn); } MEM(sz); dfs(x.S, x.F); for(int i = 0; i < n; ++i) { int mx = max({n - sz[x.S], sz[x.S] - sz[i], sz[i]}); int mn = min({n - sz[x.S], sz[x.S] - sz[i], sz[i]}); ans = min(ans, mx - mn); } } cout << ans << '\n'; } int main() { cin.tie(0), ios::sync_with_stdio(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...