제출 #1187689

#제출 시각아이디문제언어결과실행 시간메모리
1187689MatteoArcariClosing Time (IOI23_closing)C++20
8 / 100
106 ms31888 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; int max_score(int n, int x, int y, ll k, vi u, vi v, vi w) { vector<vector<pair<int, ll>>> adj(n); for (int i = 0; i < n - 1; i++) { adj[u[i]].push_back({v[i], w[i]}); adj[v[i]].push_back({u[i], w[i]}); } int ans = 2; auto calc = [&adj, &n](int _x) -> vector<ll> { vector<ll> dp(n + 1); vector<ll> dst; auto dfs = [&](auto &&dfs, int i, int p, ll d) -> void { dst.push_back(d); for (auto [j, w]: adj[i]) { if (j == p) continue; dfs(dfs, j, i, d + w); } }; dfs(dfs, _x, -1, 0); assert(dst.size() == n); sort(dst.rbegin(), dst.rend()); for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + dst.back(); dst.pop_back(); } return dp; }; vector<ll> dpX = calc(x); vector<ll> dpY = calc(y); ans = -1; for (int sus = 1 << 18; sus; sus >>= 1) { int sum = ans + sus; if (sum > n) continue; for (int i = 0; i <= sum; i++) { if (dpX[i] + dpY[sum - i] <= k) { ans = sum; break; } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...