제출 #1226210

#제출 시각아이디문제언어결과실행 시간메모리
1226210mariaclara봉쇄 시간 (IOI23_closing)C++20
43 / 100
238 ms32908 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++; } cam.clear(); vector<bool> vis(N); 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++; vis[i] = 1; cam.insert({distX[Y] - 2*min(distX[i], distY[i]), i}); } else cam.insert({min(distX[i], distY[i]), i}); } if(at_val > K) ans2 = 0; while(!cam.empty() and at_val <= K) { auto [D, ind] = *cam.begin(); cam.erase(cam.begin()); if(!vis[ind]) { vis[ind] = 1; cam.insert({max(distX[ind], distY[ind]) - D, ind}); } at_val += D; if(at_val > K) break; ans2++; } 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...