Submission #1201276

#TimeUsernameProblemLanguageResultExecution timeMemory
1201276PagodePaivaClosing Time (IOI23_closing)C++20
0 / 100
60 ms21828 KiB
#include "closing.h" #include<bits/stdc++.h> using namespace std; const long long N = 200010; vector <pair <long long, long long>> g[N]; long long mark[N]; int max_score(int n, int X, int Y, long long k, std::vector<int> U, std::vector<int> V, std::vector<int> W){ for(int i = 0;i < n;i++){ g[i].clear(); mark[i] = 0; } for(long long i = 0;i < n-1;i++){ g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); } priority_queue <pair <long long, long long>> pq; for(auto [v, w] : g[X]){ pq.push({-w, v}); } for(auto [v, w] : g[Y]){ pq.push({-w, v}); } long long ans = 0, sum = 0;; while(!pq.empty()){ auto [w, v] = pq.top(); pq.pop(); if(mark[v]) continue; w *= -1; if(sum+w > k){ return ans; } sum += w; ans++; mark[v] = 1; for(auto [x, ww] : g[v]){ if(mark[x]) continue; pq.push({-(ww+w), x}); } } 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...