Submission #563713

#TimeUsernameProblemLanguageResultExecution timeMemory
563713hoanghq2004Mousetrap (CEOI17_mousetrap)C++14
45 / 100
792 ms87592 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]; 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() { // freopen("mousetrap.inp", "r", stdin); 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]); reverse(path.begin(), path.end()); int need = 0; for (auto u: path) { for (auto v: g[u]) { if (flag[v]) continue; if (v == T) continue; ++need; dfs(v, u); s[u].push_back(f[v]); } } for (int u = 1; u <= n; ++u) { sort(s[u].begin(), s[u].end()); reverse(s[u].begin(), s[u].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] + need > limit) { --k; if (k < 0) return 0; ++tot; ++i; } } if (tot > limit) return 0; return 1; }; int L = need, 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:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while (i < s[u].size() && s[u][i] + need > limit) {
      |                    ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         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...