제출 #538998

#제출 시각아이디문제언어결과실행 시간메모리
538998syl123456Mousetrap (CEOI17_mousetrap)C++17
20 / 100
213 ms524288 KiB
#pragma GCC diagnostic ignored "-Wunused-parameter" #pragma GCC diagnostic ignored "-Wunused-variable" #pragma GCC diagnostic ignored "-Wparentheses" #include <bits/stdc++.h> #define all(i) (i).begin(), (i).end() #define random random_device rd; mt19937 rng(rd()) using namespace std; template<typename T1, typename T2> ostream& operator << (ostream &i, pair<T1, T2> j) { return i << j.first << ' ' << j.second; } template<typename T> ostream& operator << (ostream &i, vector<T> j) { i << '{' << j.size() << ':'; for (T ii : j) i << ' ' << ii; return i << '}'; } void Debug(bool _split) {} template<typename T1, typename ...T2> void Debug(bool _split, T1 x, T2 ...args) { if (_split) cerr << ", "; cerr << x, Debug(true, args...); } template<typename T> void Debuga(T *i, int n) { cerr << '['; for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1]; cerr << endl; } #ifdef SYL #define debug(args...) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << "]\u001b[0m" << endl #define debuga(i) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name())), cerr << "\u001b[0m" #else #define debug(args...) void(0) #define debuga(i) void(0) #endif typedef long long ll; typedef pair<int, int> pi; const int inf = 0x3f3f3f3f, lg = 20; const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f; vector<vector<int>> g, dp, pa; vector<int> c, d, dep; int n, s, t; void dfs1(int i, int p, int _d) { pa[i][0] = p, dep[i] = i == s ? 0 : dep[p] + 1; if (i == t) return c[i] = _d, d[i] = 0, void(); c[i] = _d + g[i].size() - (i != s); for (int j : g[i]) if (j != p) dfs1(j, i, c[i]); } int lca(int i, int j) { if (dep[i] < dep[j]) swap(i, j); for (int x = lg - 1; ~x; --x) if (dep[pa[i][x]] >= dep[j]) i = pa[i][x]; for (int x = lg - 1; ~x; --x) if (pa[i][x] != pa[j][x]) i = pa[i][x], j = pa[j][x]; return i == j ? i : pa[i][0]; } void build() { for (int i = 1; i < lg; ++i) for (int j = 0; j < n; ++j) pa[j][i] = pa[pa[j][i - 1]][i - 1]; for (int i = 0; i < n; ++i) if (~dep[i]) { int x = lca(i, t); d[i] = c[i] + c[pa[t][0]] - c[x] - (x != s ? c[pa[x][0]] : 0) - dep[t] + dep[x]; } } bool dfs2(int i, int p) { if (i == t) return fill(all(dp[i]), d[i]), true; vector<vector<int>> v(n + 1); int ch = -1; for (int j : g[i]) if (j != p) { if (dfs2(j, i)) { ch = j; continue; } for (int x = 0; x <= n; ++x) v[x].push_back(dp[j][x]); } for (int j = 0; j <= n; ++j) sort(all(v[j]), [](int x, int y) {return x > y;}); int sz = v[0].size(); for (int j = 0; j <= n; ++j) { dp[i][j] = inf; for (int x = 0; x <= j; ++x) { if (j - x + 1 > n || x > sz) continue; if (x == sz) { if (~ch) dp[i][j] = min(dp[i][j], x + dp[ch][j - x + 1]); else dp[i][j] = min(dp[i][j], d[i]); break; } if (~ch) dp[i][j] = min(dp[i][j], max(x + dp[ch][j - x + 1], v[j - x + 1][x])); else dp[i][j] = min(dp[i][j], v[j - x + 1][x]); } } return ch != -1; } signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> t >> s; if (s == t) return cout << 0, 0; --s, --t; g.resize(n), dp.assign(n, vector<int>(n + 1)); d.resize(n), dep.assign(n, -1), c.resize(n), pa.assign(n, vector<int>(lg)); for (int i = 0; i < n - 1; ++i) { int x, y; cin >> x >> y; --x, --y; g[x].push_back(y), g[y].push_back(x); } dfs1(s, s, 0); build(); dfs2(s, -1); cout << dp[s][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...