Submission #1096429

#TimeUsernameProblemLanguageResultExecution timeMemory
1096429Mike_VuMousetrap (CEOI17_mousetrap)C++14
0 / 100
258 ms72272 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define MASK(x) (1LL<<(x)) #define BITj(x, j) (((x)>>(j))&1) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } const int maxn = 1e6+5; int n, s, t; vector<int> a[maxn]; priority_queue<int> q; int h[maxn], sumpath = 0; int calcost(int u, int p) { if ((int)a[u].size() < 3) { //cannot continue return (int)a[u].size(); } int ma1 = 0, ma2 = 0; for (int v : a[u]) { if (v == p) continue; int val = calcost(v, u); if (val > ma1){ ma2 = ma1; ma1 = val; } else if (val > ma2){ ma2 = val; } } // cout << "calcost " << u << ' ' << ma2+(int)a[u].size()-1 << "\n"; return ma2+(int)a[u].size()-1; } bool dfs(int u, int p) { if (u == t) return 1; //check int nxt = -1; for (int v : a[u]) { if (v == p) continue; h[v] = h[u]+1; if (dfs(v, u)) { nxt = v; } } if (nxt == -1) return 0; for (int v : a[u]) { if (v == nxt || v == p) continue; int val = calcost(v, u); q.push(val+(int)a[u].size()-2+(u==s)+h[u]); } if (!q.empty()) { q.pop(); sumpath++; } return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } cin >> n >> t >> s; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; a[u].pb(v); a[v].pb(u); } //block all except the mouse's chosen path h[s] = 0; dfs(s, -1); cout << (q.empty() ? sumpath : q.top()); } /* 10 1 7 1 2 2 3 2 4 3 9 3 5 4 7 4 6 6 8 7 10 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...