Submission #1206834

#TimeUsernameProblemLanguageResultExecution timeMemory
1206834PekibanClosing Time (IOI23_closing)C++20
0 / 100
67 ms23876 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> pq; bool vis[2][N], t[N]; vector<array<ll, 2>> g[N]; ll di[2][N]; fill(t, t+N, 0); for (int i = 0; i < 2; ++i) { fill(vis[i], vis[i]+N, 0); fill(di[i], di[i]+N, 1e18); } for (int i = 0; i < N; ++i) g[U[i]].pb({V[i], W[i]}), g[V[i]].pb({U[i], W[i]}); pq.push({0, X, 0}); pq.push({0, Y, 1}); di[0][X] = di[1][Y] = 0; int ans = 0; while (!pq.empty()) { auto [D, s, id] = pq.top(); pq.pop(); // cout << D << ' ' << s << ' ' << id << ' ' << t[s] << endl; if (vis[id][s]) continue; bool ok = 0; if (t[s] && K >= D-di[id^1][s]) K -= D-di[id^1][s], ans++, ok = 1; if (!t[s] && K >= D) K -= D, ans++, t[s] = 1, ok = 1; vis[id][s] = 1; if (!ok) continue; for (auto [u, w] : g[s]) { if (vis[id][u]) continue; if (di[id][u] > di[id][s] + w) { di[id][u] = di[id][s] + w; pq.push({di[id][u], u, id}); } } } 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...