Submission #1248820

#TimeUsernameProblemLanguageResultExecution timeMemory
1248820madamadam3Closing Time (IOI23_closing)C++20
0 / 100
67 ms20548 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; typedef long long ll; struct Edge { int u, v, w; }; int n, x, y; ll k; vi xi, yi, wi; vector<vector<Edge>> adj; const ll INF = 4e18; int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) { n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W; adj.assign(n, vector<Edge>()); for (int i = 0; i < n - 1; i++) { adj[xi[i]].push_back(Edge{yi[i], wi[i]}); adj[yi[i]].push_back(Edge{xi[i], wi[i]}); } int ans = 0; ll tl = 0; priority_queue<pair<ll, int>> xq, yq; xq.push({0, x}), yq.push({0, y}); while (tl <= k && !xq.empty() && !yq.empty()) { pair<ll, int> xc = xq.empty() ? make_pair(INF, -1) : xq.top(); pair<ll, int> yc = yq.empty() ? make_pair(INF, -1) : yq.top(); if (xc.first < yc.first) { xq.pop(); if (tl + xc.first > k) break; ans++; tl += xc.first; } else { yq.pop(); if (tl + yc.first > k) break; ans++; tl += yc.first; } } 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...