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 <bits/stdc++.h>
using namespace std;
struct Arc {int v;int d;};
vector <Arc> gr[200000];
long long dist[400001];
long long d;
int nd;
bool fix[200000];
void dfs (int u) {
fix[u] = 1;
for (int i = 0; i < (int)gr[u].size(); i++) {
int v = gr[u][i].v;
if (!fix[v]) {
nd++;
d+=gr[u][i].d;
dist[nd] = d;
dfs(v);
d-=gr[u][i].d;
}
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
Arc tmp;
for (int i = 0; i < N; i++) {
gr[i].clear();
fix[i] = 0;
}
for (int i = 0; i <= 2*N; i++) {
dist[i] = 0;
}
for (int i = 0; i < N; i++) {
tmp.v=V[i];
tmp.d = W[i];
gr[U[i]].push_back(tmp);
tmp.v=U[i];
gr[V[i]].push_back(tmp);
}
d = 0;
nd = 0;
dist[0] = 0;
dfs(X);
for (int i = 0; i < N; i++) {
fix[i] = 0;
}
d = 0;
nd++;
dist[nd] = 0;
dfs(Y);
sort(dist,dist+nd+1);
int ans = 0; long long sum = 0;
for (int i = 0; i < 2*N; i++) {
if (sum + dist[i] > K) {
break;
} else {
sum += dist[i];
ans++;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |