Submission #1226230

#TimeUsernameProblemLanguageResultExecution timeMemory
1226230mariaclaraClosing Time (IOI23_closing)C++20
55 / 100
1098 ms35848 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef vector<int> vi; typedef vector<ll> vl; #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb push_back #define mk make_pair #define fr first #define sc second vl calc_dist(int X, vector<vector<pii>> edges) { int N = sz(edges); vl dist(N, 1e12); vi vis(N); priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({0,X}); dist[X] = 0; while(!pq.empty()) { auto [D,at] = pq.top(); pq.pop(); if(vis[at]) continue; vis[at] = 1; for(auto [viz, peso] : edges[at]) { if(dist[viz] > D + peso) { dist[viz] = D + peso; pq.push({D+peso, viz}); } } } return dist; } int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) { vector<vector<pii>> edges(N); for(int i = 0; i+1 < N; i++) edges[U[i]].pb({V[i], W[i]}), edges[V[i]].pb({U[i], W[i]}); vl distX = calc_dist(X, edges), distY = calc_dist(Y, edges); set<pli> cam; for(int i = 0; i < N; i++) cam.insert({min(distX[i], distY[i]), i}); int ans1 = 0, ans2 = 0; ll at_val = 0; while(!cam.empty()) { auto [D, ind] = *cam.begin(); cam.erase(cam.begin()); at_val += D; if(at_val > K) break; ans1++; } vector<bool> vis(N); vl dp(2*N+1, K+1); at_val = 0; for(int i = 0; i < N; i++) { if(distX[Y] == distX[i] + distY[i]) at_val += min(distX[i], distY[i]), ans2++; } dp[ans2] = at_val; ans2 = 0; for(int i = 0; i < N; i++) { ll mi = min(distX[i], distY[i]), ma = max(distX[i], distY[i]); if(distX[Y] == distX[i] + distY[i]) mi = distX[Y] - 2*mi, ma = K+1; for(int qtd = 2*N; qtd > 0; qtd--) dp[qtd] = min({dp[qtd], dp[qtd-1] + mi, dp[qtd-2] + ma}); } for(int qtd = 0; qtd <= 2*N; qtd++) if(dp[qtd] <= K) ans2 = qtd; return max(ans1, ans2); }
#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...