#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int MAXN=5e5+5;
const int LOG=20;
int n;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];
void dfs(int node, int rod, ll d) {
par[0][node]=rod;
dist[node]=d;
dep[node]=dep[rod]+1;
// printf("node: %d, dist: %lld, dep: %d, par: %d\n", node, dist[node], dep[node], rod);
for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, d+sus.Y);
}
void rek(int node) {
for (pii sus:ls[node]) {
if (sus.X!=par[0][node]) {
rek(sus.X);
da[node]=min(da[node], da[sus.X]+sus.Y);
db[node]=min(db[node], db[sus.X]+sus.Y);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for (int i=0; i<n-1; ++i) {
ls[A[i]].pb(mp(B[i], D[i]));
ls[B[i]].pb(mp(A[i], D[i]));
}
dfs(0, 0, 0);
}
long long Query(int S, int x[], int T, int y[]) {
for (int i=0; i<n; ++i) da[i]=db[i]=MAX;
for (int i=0; i<S; ++i) da[x[i]]=0;
for (int i=0; i<T; ++i) db[y[i]]=0;
rek(0);
ll sol=MAX;
for (int i=0; i<n; ++i) sol=min(sol, da[i]+db[i]);
return sol;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
12396 KB |
Output is correct |
2 |
Correct |
861 ms |
20516 KB |
Output is correct |
3 |
Correct |
952 ms |
20716 KB |
Output is correct |
4 |
Correct |
955 ms |
20716 KB |
Output is correct |
5 |
Correct |
1094 ms |
20972 KB |
Output is correct |
6 |
Correct |
556 ms |
30316 KB |
Output is correct |
7 |
Correct |
985 ms |
30316 KB |
Output is correct |
8 |
Correct |
967 ms |
30188 KB |
Output is correct |
9 |
Correct |
1108 ms |
30444 KB |
Output is correct |
10 |
Correct |
541 ms |
30060 KB |
Output is correct |
11 |
Correct |
946 ms |
30060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
12268 KB |
Output is correct |
2 |
Execution timed out |
8087 ms |
57564 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
12396 KB |
Output is correct |
2 |
Correct |
861 ms |
20516 KB |
Output is correct |
3 |
Correct |
952 ms |
20716 KB |
Output is correct |
4 |
Correct |
955 ms |
20716 KB |
Output is correct |
5 |
Correct |
1094 ms |
20972 KB |
Output is correct |
6 |
Correct |
556 ms |
30316 KB |
Output is correct |
7 |
Correct |
985 ms |
30316 KB |
Output is correct |
8 |
Correct |
967 ms |
30188 KB |
Output is correct |
9 |
Correct |
1108 ms |
30444 KB |
Output is correct |
10 |
Correct |
541 ms |
30060 KB |
Output is correct |
11 |
Correct |
946 ms |
30060 KB |
Output is correct |
12 |
Correct |
13 ms |
12268 KB |
Output is correct |
13 |
Execution timed out |
8087 ms |
57564 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |