Submission #856041

#TimeUsernameProblemLanguageResultExecution timeMemory
856041CyanmondMousetrap (CEOI17_mousetrap)C++17
100 / 100
806 ms205748 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define per(i, l, r) for (int i = (r - 1); i >= l; --i) #define ALL(x) (x).begin(), (x).end() using i64 = long long; void main_() { int N, T, M; cin >> N >> T >> M; --T, --M; if (T == M) { cout << 0 << endl; return; } vector<int> A(N - 1), B(N - 1); vector<vector<int>> Tree(N); rep(i, 0, N - 1) { cin >> A[i] >> B[i]; Tree[--A[i]].push_back(--B[i]); Tree[B[i]].push_back(A[i]); } vector<bool> isPath(N); vector<int> path; auto dfs = [&](auto &&self, const int v, const int p) -> bool { bool ret = false; for (const int t : Tree[v]) { if (t == p) continue; ret |= self(self, t, v); } if (v == T) ret = true; isPath[v] = ret; if (ret) path.push_back(v); return ret; }; dfs(dfs, M, -1); reverse(ALL(path)); vector<int> dp(N); auto dfs2 = [&](auto &&self, const int v, const int p) -> int { vector<int> vals; for (const int t : Tree[v]) { if (t == p) continue; if (isPath[t]) continue; vals.push_back(self(self, t, v)); } sort(ALL(vals), greater()); int cost = -1; if (vals.empty()) cost = 0; else if (vals.size() == 1) cost = 1; else cost = vals[1] + (int)(vals.size()) - 1; dp[v] = cost; return dp[v] + 1; }; for (const auto e : path) { if (e == T) continue; dfs2(dfs2, e, -1); } i64 ans = 1ll << 60; int S = (int)path.size(); vector<int> rs(S); per(i, 1, S) { rs[i - 1] = rs[i] + (int)Tree[path[i - 1]].size() - 2; } vector<vector<int>> cList(S); rep(i, 0, S - 1) { vector<int> vals; for (const int t : Tree[path[i]]) { if (isPath[t]) continue; vals.push_back(dp[t]); } sort(ALL(vals), greater()); rep(j, 0, (int)vals.size()) cList[i].push_back(vals[j] + (int)vals.size() - j); } int ok = 1 << 30, ng = -1; while (ok - ng > 1) { const auto m = (ok + ng) / 2; int cnt1 = 0; bool isOk = true; rep(i, 0, S - 1) { int baseCost = rs[i + 1]; int lm1 = -1, lm2 = -1; rep(j, 0, (int)cList[i].size()) { if (lm1 == -1 and cnt1 + j + cList[i][j] + baseCost <= m) { lm1 = j; } if (lm2 == -1 and cnt1 + j + cList[i][j] + 2 + baseCost <= m) { lm2 = j; } } if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size(); if (lm2 != -1 and cnt1 + lm2 + 1 <= i + 1) { break; } if (lm1 == -1) { isOk = false; break; } cnt1 += lm1; if (cnt1 > i + 1) { isOk = false; break; } } (isOk ? ok : ng) = m; } cout << ok << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); main_(); }

Compilation message (stderr)

mousetrap.cpp: In function 'void main_()':
mousetrap.cpp:101:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  101 |             if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mousetrap.cpp:65:9: warning: unused variable 'ans' [-Wunused-variable]
   65 |     i64 ans = 1ll << 60;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...