Submission #763499

#TimeUsernameProblemLanguageResultExecution timeMemory
763499fanwenPapričice (COCI20_papricice)C++17
110 / 110
198 ms23360 KiB
/** * author : pham van sam * created : 22 June 2023 (Thursday) **/ #include <bits/stdc++.h> using namespace std; using namespace chrono; #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for (int i = 0, _n = n; i < _n; ++i) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it) template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; } template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; } const int MAXN = 2e5 + 5; int N, num_child[MAXN], ans; vector <int> adj[MAXN]; void dfs(int u, int p) { num_child[u] = 1; for (auto v : adj[u]) if(v != p) { dfs(v, u); num_child[u] += num_child[v]; } } int get(int a, int b, int c) { if(a > b) swap(a, b); return max(b, c) - min(a, c); } set <int> same, diff; vector <int> optimize(set <int> &s, int res) { auto it = s.upper_bound(res); vector <int> ans; if(it != s.end()) ans.push_back(*it); if(it != s.begin()) it--, ans.push_back(*it); return ans; } void calc(int u, int p) { for (auto x : optimize(same, (N + num_child[u]) / 2)) minimize(ans, get(num_child[u], x - num_child[u], N - x)); for (auto x : optimize(diff, (N - num_child[u]) / 2)) minimize(ans, get(num_child[u], x, N - num_child[u] - x)); same.insert(num_child[u]); for (auto v : adj[u]) if(v != p) calc(v, u); same.erase(num_child[u]); diff.insert(num_child[u]); } void process(void) { cin >> N; FOR(i, 2, N) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 0); ans = N; calc(1, 0); cout << ans; } signed main() { #define TASK "TASK" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); auto start_time = steady_clock::now(); int test = 1; // cin >> test; for (int i = 1; i <= test; ++i) { process(); // cout << '\n'; } auto end_time = steady_clock::now(); cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); }

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...