# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1080997 | Kipras | Soccer Stadium (IOI23_soccer) | 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 <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxN = 2e5+10;
vector<pair<ll, ll>> adj[maxN];
ll been[maxN];
int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W){
for(int i = 0; i <= n; i++)been[i]=0;
been[x]=1;
been[y]=1;
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]});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> q;
for(auto i : adj[x]) {
q.push(i);
}
for(auto i : adj[y]) {
q.push(i);
}
ll res = 0;
while(!q.empty()) {
ll v = q.top().first, w = q.top().second;
if(w>k)break;
k-=w;
res++;
for(auto i : adj[v]) {
if(been[i.first])continue;
q.push({i.first, w+i.second});
}
}
return res;
}