#include "factories.h"
#include<algorithm>
#define INF 99999999999999999LL
using namespace std;
int L[1000010];
int nxt[1000010], pv[1000010], ed[1000010];
int n, Q[500010], pp[23][500010], sz, pcnt[500010];
int D[500010], par[500010];
long long D2[500010], dist[23][500010];
bool chk[500010];
void BFS(int a){
int h = 0, t = 0, i, x;
Q[++t] = a, D2[a] = 0, D[a] = 1;
while (h < t){
x = Q[++h];
for (i = pv[x]; i; i = nxt[i]){
if (!D[ed[i]] && !chk[ed[i]]){
Q[++t] = ed[i];
D2[ed[i]] = D2[x] + L[i];
D[ed[i]] = 1;
par[ed[i]] = x;
}
}
}
sz = t;
}
int Get_mid(int a){
int i, x;
BFS(a);
for (i = sz; i >= 1; i--){
x = Q[i];
if (D[x] > sz / 2) break;
D[par[x]] += D[x];
}
for (i = 1; i <= sz; i++){
D[Q[i]] = 0;
}
return x;
}
void DFS(int a, int ppar, int pdis){
int i, mid, x;
mid = Get_mid(a);
if (sz == 1){
pp[pcnt[a]][a] = a;
dist[pcnt[a]][a] = 0;
pcnt[a]++;
pp[pcnt[a]][a] = ppar;
dist[pcnt[a]][a] = pdis;
pcnt[a]++;
return;
}
chk[mid] = true;
for (i = pv[mid]; i; i = nxt[i]){
x = ed[i];
if (!chk[x]){
DFS(x, mid, L[i]);
}
}
pp[pcnt[mid]][mid] = mid;
dist[pcnt[mid]][mid] = 0;
pcnt[mid]++;
chk[mid] = false;
if (ppar == -1)return;
BFS(a);
for (i = 1; i <= sz; i++){
x = Q[i];
D[x] = 0;
pp[pcnt[x]][x] = ppar;
dist[pcnt[x]][x] = D2[x] + pdis;
pcnt[x]++;
}
}
long long Len[500010];
void Init(int N, int A[], int B[], int D[]) {
int i, cnt = 0;
for (i = 0; i < N - 1; i++){
nxt[++cnt] = pv[A[i]]; ed[cnt] = B[i]; pv[A[i]] = cnt; L[cnt] = D[i];
nxt[++cnt] = pv[B[i]]; ed[cnt] = A[i]; pv[B[i]] = cnt; L[cnt] = D[i];
}
DFS(0, -1, 0);
for (i = 0; i < N; i++)Len[i] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
register int i, j, x;
long long Res = INF, t;
for (i = 0; i != S; i++){
x = X[i];
for (j = 0; j != pcnt[x]; j++){
if (Len[pp[j][x]] > dist[j][x]) Len[pp[j][x]] = dist[j][x];
}
}
for (i = 0; i != T; i++){
x = Y[i];
for (j = 0; j != pcnt[x]; j++){
t = Len[pp[j][x]] + dist[j][x];
if (Res > t) Res = t;
}
}
for (i = 0; i != S; i++){
x = X[i];
for (j = 0; j != pcnt[x]; j++){
Len[pp[j][x]] = INF;
}
}
return Res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
189864 KB |
Output is correct |
2 |
Correct |
388 ms |
189864 KB |
Output is correct |
3 |
Correct |
460 ms |
189864 KB |
Output is correct |
4 |
Correct |
436 ms |
189864 KB |
Output is correct |
5 |
Correct |
448 ms |
189864 KB |
Output is correct |
6 |
Correct |
288 ms |
189864 KB |
Output is correct |
7 |
Correct |
424 ms |
189864 KB |
Output is correct |
8 |
Correct |
424 ms |
189864 KB |
Output is correct |
9 |
Correct |
444 ms |
189864 KB |
Output is correct |
10 |
Correct |
272 ms |
189864 KB |
Output is correct |
11 |
Correct |
400 ms |
189864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
189864 KB |
Output is correct |
2 |
Correct |
5412 ms |
189864 KB |
Output is correct |
3 |
Execution timed out |
6000 ms |
189860 KB |
Program timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6000 ms |
189860 KB |
Program timed out |
2 |
Halted |
0 ms |
0 KB |
- |