Submission #1217397

#TimeUsernameProblemLanguageResultExecution timeMemory
1217397fastClosing Time (IOI23_closing)C++20
8 / 100
93 ms21828 KiB
#include "closing.h" #include "bits/stdc++.h" using namespace std; #define vec vector int max_score(int N, int X, int Y, long long K, vec<int> U, vec<int> V, vec<int> W) { vec<vec<pair<int, int>>> 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]}); } auto dijkstra = [&](int src) { const long long INF = LLONG_MAX / 4; vec<long long> dist(N, INF); dist[src] = 0; priority_queue<pair<long long, int>, vec<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto &e : adj[u]) { int v = e.first; long long w = e.second; if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } return dist; }; vec<long long> dx = dijkstra(X); vec<long long> dy = dijkstra(Y); vec<long long> dist(N); for (int i = 0; i < N; ++i) { dist[i] = min(dx[i], dy[i]); } sort(dist.begin(), dist.end()); long long used = 0; int cnt = 0; for (auto d : dist) { if (used + d > K) break; used += d; ++cnt; } return cnt; }
#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...