# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
980802 | Gr1sen | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"closing.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
//#include"grader.cpp"
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pi pair<ll, ll>
#define vp vector<pi>
#define vvp vector<vp>
#define pq priority_queue<tuple<ll, ll, ll>>
#define g(y,x) get<x>(y)
pq Q;
vvp Adj;
vi V;
ll max_score(ll n, ll x, ll y, ll k, vi U, vi V, vi W) {
Q = pq();
Adj = vvp(n);
V = vi(n, -1);
for (int i = 0; i < n; i++) {
int a = U[i], b = V[i], w = W[i];
Adj[a].push_back({b, w});
Adj[b].push_back({a, w});
}
Q.push({0, x, 0});
Q.push({0, y, 1});
ll k1 = k;
ll t = 0;
while(!Q.empty()) {
auto a = Q.top();
Q.pop();
if (~V[g(a,1)]) continue;
if (-g(a,0) > k1) break;
V[g(a,1)] = -g(a,0);
t++;
k1 += g(a,0);
for (auto i : Adj[g(a,1)]) {
Q.push({g(a,0)-i.second, i.first, g(a,2)});
}
}
return t;
}