Submission #468705

#TimeUsernameProblemLanguageResultExecution timeMemory
468705paga2004Mousetrap (CEOI17_mousetrap)C++14
0 / 100
5046 ms78568 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #ifdef LOCAL #define dbg(x) cerr << x << "\n"; #else #define dbg(x) #endif const int INF = 1e17; int n, t, m; vector<int> scores; vector<vector<int>> g; vector<int> depths; int dfs1(int v, int p) { depths[v] = depths[p] + max(0ll, (int)g[v].size() - 2); if (v == t) { depths[v] = 0; } vector<int> besties; for (int w : g[v]) { if (w == p) continue; int thisscore = dfs1(w, v); if (thisscore < 0) continue; besties.push_back(dfs1(w, v)); } sort(besties.begin(), besties.end()); int score = besties.size(); if ((int)g[v].size() == 1) score = 1; if (v == t) { score = 0; } if (besties.size() >= 2) { score += besties[besties.size() - 2]; } scores[v] = score; if (v == m) { return -score; } return score; } int dfs2(int v, int p) { dbg("v " << v << " blocks " << depths[p]); int score = -INF; if (v == m) { score = 0; dbg("heerer " << depths[p] + scores[v]); for (int w : g[v]) { if (w == p) continue; score = max(depths[v] + scores[w] + 1, score); } dbg("Score at m: " << score); return score; } for (int w : g[v]) { if (w == p) continue; score = max(dfs2(w, v), score); dbg("current score #" << w << ": " << score); } if (score != -INF) { return max(score, depths[p] - 2 + scores[v]); } return -INF; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> t >> m; t--; m--; if (t == m) { cout << "0\n"; exit(0); } g.resize(n); scores.resize(n); depths.resize(n); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } depths[t] = 1; dfs1(t, t); dbg("scores"); for (int i = 0; i < n; i++) { cout << scores[i] << " "; } cout << "\n"; dbg("depths"); for (int i = 0; i < n; i++) { cout << depths[i] << " "; } cout << "\n"; cout << dfs2(t, t) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...