Submission #563728

#TimeUsernameProblemLanguageResultExecution timeMemory
563728hoanghq2004Mousetrap (CEOI17_mousetrap)C++14
100 / 100
1020 ms195936 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, S, T; vector <int> g[N]; int f[N], flag[N]; int cnt; void dfs(int u, int p) { int best[3] = {0, 0, 0}; for (auto v: g[u]) { if (v == p) continue; dfs(v, u); best[2] = f[v]; sort(best, best + 3); reverse(best, best + 3); } f[u] = best[1] + g[u].size() - 1; } int par[N]; void init(int u, int p) { par[u] = p; for (auto v: g[u]) { if (v == p) continue; init(v, u); } } vector <int> s[N]; int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> T >> S; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } init(S, 0); vector <int> path; for (int u = T; u != S; u = par[u]) flag[par[u]] = 1, path.push_back(par[u]); int need = 0; for (auto u: path) { for (auto v: g[u]) { if (flag[v]) continue; if (v == T) continue; dfs(v, u); s[u].push_back(f[v]); } sort(s[u].begin(), s[u].end()); for (auto& x: s[u]) x += ++need; reverse(s[u].begin(), s[u].end()); } reverse(path.begin(), path.end()); auto check = [&](int limit) { int k = 0, tot = 0; for (auto u: path) { ++k; int i = 0; while (i < s[u].size() && s[u][i] + tot > limit) { --k; if (k < 0) return 0; ++tot; ++i; } } if (tot > limit) return 0; return 1; }; int L = 0, R = n; while (L < R) { int mid = L + R >> 1; if (check(mid)) R = mid; else L = mid + 1; } cout << L; }

Compilation message (stderr)

mousetrap.cpp: In lambda function:
mousetrap.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             while (i < s[u].size() && s[u][i] + tot > limit) {
      |                    ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:79:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int mid = L + R >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...