Submission #1075553

#TimeUsernameProblemLanguageResultExecution timeMemory
1075553c2zi6Closing Time (IOI23_closing)C++17
43 / 100
149 ms41808 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "closing.h" namespace GREEDY { int n; VVPI gp; void dfs(VL& dist, int u, int p = -1) { for (auto[v, w] : gp[u]) if (v != p) { dist[v] = dist[u] + w; dfs(dist, v, u); } } VL distx, disty; int max_score(int N, int X, int Y, ll K, VI U, VI V, VI W) { n = N; gp = VVPI(n); rep(i, n-1) { auto[u, v, w] = make_tuple(U[i], V[i], W[i]); gp[u].pb({v, w}); gp[v].pb({u, w}); } distx = disty = VL(n); dfs(distx, X); dfs(disty, Y); VL a; for (ll x : distx) a.pb(x); for (ll x : disty) a.pb(x); sort(all(a)); a.pb(2e18); int ans = 0; for (ll x : a) { if (x <= K) { K -= x; ans++; } else break; } return ans; } }; namespace LINEAR { int max_score(int N, int X, int Y, ll K, VI U, VI V, VI W) { int greedyans = GREEDY::max_score(N, X, Y, K, U, V, W); int n = N; VI a = W; if (Y < X) swap(X, Y); VL distx = GREEDY::distx; VL disty = GREEDY::disty; int ans = 0; priority_queue<PLL> pq; rep(i, n) { if (i < X) pq.push({-distx[i], -(disty[i]-distx[i])}); else if (i > Y) pq.push({-disty[i], -(distx[i]-disty[i])}); else { ll mx = max(distx[i], disty[i]); ll mn = min(distx[i], disty[i]); pq.push({-(mx-mn), +1}); K -= mn; ans++; if (K < 0) return greedyans; } } while (pq.size()) { auto[cost, nxt] = pq.top(); pq.pop(); K += cost; if (K < 0) break; ans++; if (nxt != +1) pq.push({nxt, +1}); } return max(greedyans, ans); } }; int max_score(int N, int X, int Y, ll K, VI U, VI V, VI W) { return LINEAR::max_score(N, X, Y, K, U, V, W); return GREEDY::max_score(N, X, Y, K, U, V, W); }
#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...