제출 #984481

#제출 시각아이디문제언어결과실행 시간메모리
984481duckindogMousetrap (CEOI17_mousetrap)C++17
100 / 100
869 ms214356 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1'000'000 + 10; int n, t, m; vector<int> ad[N]; vector<int> path; bool inPath[N]; bool dfs1(int u, int p = -1) { inPath[u] = u == t; for (const auto& v : ad[u]) { if (v == p) continue; inPath[u] |= dfs1(v, u); } if (inPath[u]) path.push_back(u); return inPath[u]; } int f[N]; void dfs2(int u, int p = -1) { vector<int> best {0, 0}; for (const auto& v : ad[u]) { if (v == p || inPath[v]) continue; dfs2(v, u); best.push_back(f[v]); } sort(best.begin(), best.end(), greater<>()); f[u] = best.size() + best[1] - 2; // cerr << u << " "; // for (const auto& x : best) cerr << x << " "; cerr << "\n"; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> t >> m; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; ad[u].push_back(v); ad[v].push_back(u); } dfs1(m); vector<pair<int, int>> value; { reverse(path.begin(), path.end()); path.pop_back(); int it = 0; for (const auto& u : path) { vector<int> best; for (const auto& v : ad[u]) { if (inPath[v]) continue; dfs2(v, u); best.push_back(f[v]); } sort(best.begin(), best.end(), greater<>()); for (const auto& x : best) value.push_back({x, it + 1}); it += 1; } } for (int i = 0; i < value.size(); ++i) value[i].first += value.size() - i; auto chk = [&](int mid) { int it = 0; for (const auto& [val, d] : value) { if (it + val > mid) { if (it >= d) return false; it += 1; } } return it <= mid; }; int l = 0, r = n * 2, it = 0; while (l <= r) { int mid = l + r >> 1; if (chk(mid)) r = (it = mid) - 1; else l = mid + 1; } cout << it << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

mousetrap.cpp: In function 'int32_t main()':
mousetrap.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < value.size(); ++i) value[i].first += value.size() - i;
      |                  ~~^~~~~~~~~~~~~~
mousetrap.cpp:80:15: 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...