#include "factories.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll SZ = 5e5 + 10, INF = 1e9 * 1e9;
int sizes[SZ], x[SZ], y[SZ];
bool used[SZ];
vector<vector<pair<ll, ll>>> vec;
vector<vector<pair<ll, ll>>> gr;
ll curC = 0;
vector<ll> bst;
set<ll> u;
ll sz(int v, ll dist = 0, int par = -1) {
ll s = 1;
vec[v].push_back({ curC, dist });
for (auto to : gr[v]) {
if (!used[to.first] && to.first != par) {
s += sz(to.first, dist + to.second, v);
}
}
sizes[v] = s;
return s;
}
ll cntr(int v, int c, int par = -1) {
for (auto to : gr[v]) {
if (to.first != par && !used[to.first] && sizes[to.first] >= c / 2) {
return cntr(to.first, c, v);
}
}
return v;
}
void decomp(int v) {
used[v] = 1;
curC = v;
sz(v);
for (auto to : gr[v]) {
if (!used[to.first]) {
decomp(cntr(to.first, sizes[to.first]));
}
}
}
void Init(int N, int A[], int B[], int D[]) {
gr.clear();
vec.clear();
bst.clear();
gr.resize(N);
vec.resize(N);
for (int i = 0; i < N - 1; i++) {
gr[A[i]].push_back({ B[i], D[i] });
gr[B[i]].push_back({ A[i], D[i] });
}
bst.resize(N);
for (auto &c : bst) c = INF;
decomp(0);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
ll ind = X[i];
for (auto cur : vec[ind]) {
u.insert(cur.first);
bst[cur.first] = min(bst[cur.first], cur.second);
}
}
ll ans = INF;
for (int i = 0; i < T; i++) {
ll ind = Y[i];
for (auto cur : vec[ind]) {
ans = min(ans, bst[cur.first] + cur.second);
}
}
for (auto cur : u) bst[cur] = INF;
u.clear();
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1024 KB |
Output is correct |
2 |
Correct |
1018 ms |
11016 KB |
Output is correct |
3 |
Correct |
1320 ms |
11256 KB |
Output is correct |
4 |
Correct |
1206 ms |
20088 KB |
Output is correct |
5 |
Correct |
1476 ms |
20472 KB |
Output is correct |
6 |
Correct |
530 ms |
18864 KB |
Output is correct |
7 |
Correct |
1269 ms |
19960 KB |
Output is correct |
8 |
Correct |
1430 ms |
19824 KB |
Output is correct |
9 |
Correct |
1502 ms |
20460 KB |
Output is correct |
10 |
Correct |
518 ms |
18848 KB |
Output is correct |
11 |
Correct |
1276 ms |
20132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
640 KB |
Output is correct |
2 |
Correct |
3740 ms |
201788 KB |
Output is correct |
3 |
Correct |
5225 ms |
300920 KB |
Output is correct |
4 |
Correct |
1390 ms |
123864 KB |
Output is correct |
5 |
Correct |
6615 ms |
380416 KB |
Output is correct |
6 |
Correct |
6174 ms |
318676 KB |
Output is correct |
7 |
Correct |
3228 ms |
68560 KB |
Output is correct |
8 |
Correct |
891 ms |
44384 KB |
Output is correct |
9 |
Correct |
3254 ms |
79144 KB |
Output is correct |
10 |
Correct |
3294 ms |
69624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1024 KB |
Output is correct |
2 |
Correct |
1018 ms |
11016 KB |
Output is correct |
3 |
Correct |
1320 ms |
11256 KB |
Output is correct |
4 |
Correct |
1206 ms |
20088 KB |
Output is correct |
5 |
Correct |
1476 ms |
20472 KB |
Output is correct |
6 |
Correct |
530 ms |
18864 KB |
Output is correct |
7 |
Correct |
1269 ms |
19960 KB |
Output is correct |
8 |
Correct |
1430 ms |
19824 KB |
Output is correct |
9 |
Correct |
1502 ms |
20460 KB |
Output is correct |
10 |
Correct |
518 ms |
18848 KB |
Output is correct |
11 |
Correct |
1276 ms |
20132 KB |
Output is correct |
12 |
Correct |
4 ms |
640 KB |
Output is correct |
13 |
Correct |
3740 ms |
201788 KB |
Output is correct |
14 |
Correct |
5225 ms |
300920 KB |
Output is correct |
15 |
Correct |
1390 ms |
123864 KB |
Output is correct |
16 |
Correct |
6615 ms |
380416 KB |
Output is correct |
17 |
Correct |
6174 ms |
318676 KB |
Output is correct |
18 |
Correct |
3228 ms |
68560 KB |
Output is correct |
19 |
Correct |
891 ms |
44384 KB |
Output is correct |
20 |
Correct |
3254 ms |
79144 KB |
Output is correct |
21 |
Correct |
3294 ms |
69624 KB |
Output is correct |
22 |
Correct |
6553 ms |
213524 KB |
Output is correct |
23 |
Correct |
6512 ms |
219980 KB |
Output is correct |
24 |
Execution timed out |
8106 ms |
286684 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |