#include "factories.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int cnt,st[500005],ed[500005],par[500005][20],dep[500005]; long long len[500005]; bool chk[500005];
vector<pair<int, int> > grp[500005];
int lca(int x, int y)
{
if (dep[x] > dep[y]) swap(x,y);
int up = dep[y] - dep[x];
for (int i=19;i>=0;i--) if (up & (1 << i)) y = par[y][i];
if (x == y) return x;
for (int i=19;i>=0;i--){
if (par[x][i] != par[y][i]){
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
void dfs(int x)
{
chk[x] = 1;
for (auto &p : grp[x]) if (!chk[p.first]){
st[p.first] = ++cnt;
dep[cnt] = dep[st[x]] + 1;
len[cnt] = len[st[x]] + p.second;
par[cnt][0] = st[x];
for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
dfs(p.first);
}
ed[st[x]] = cnt;
}
void Init(int N, int A[], int B[], int D[])
{
for (int i=0;i<N-1;i++){
grp[A[i]].push_back(make_pair(B[i],D[i]));
grp[B[i]].push_back(make_pair(A[i],D[i]));
}
st[0] = ++cnt;
dfs(0);
}
int cand[1000000],ext[500005],pcnt; long long U[500005],V[500005],ans;
int pdfs(int x)
{
U[x] = V[x] = 1e16;
if (ext[cand[x]] == 1) U[x] = 0;
if (ext[cand[x]] == 2) V[x] = 0;
int e = x + 1;
while (e < pcnt && cand[e] <= ed[cand[x]]){
int ne = pdfs(e);
U[x] = min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
V[x] = min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
e = ne;
}
ans = min(ans,U[x]+V[x]);
ext[cand[x]] = 0;
return e;
}
long long Query(int S, int X[], int T, int Y[])
{
pcnt = 0;
for (int i=0;i<S;i++) cand[pcnt++] = st[X[i]], ext[st[X[i]]] = 1;
for (int i=0;i<T;i++) cand[pcnt++] = st[Y[i]], ext[st[Y[i]]] = 2;
sort(cand,cand+pcnt);
for (int i=1;i<S+T;i++) cand[pcnt++] = lca(cand[i-1],cand[i]);
sort(cand,cand+pcnt);
pcnt = unique(cand,cand+pcnt) - cand;
ans = 1e16;
pdfs(0);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
98188 KB |
Output is correct |
| 2 |
Correct |
960 ms |
98320 KB |
Output is correct |
| 3 |
Correct |
952 ms |
98320 KB |
Output is correct |
| 4 |
Correct |
932 ms |
98320 KB |
Output is correct |
| 5 |
Correct |
848 ms |
98336 KB |
Output is correct |
| 6 |
Correct |
868 ms |
98320 KB |
Output is correct |
| 7 |
Correct |
916 ms |
98320 KB |
Output is correct |
| 8 |
Correct |
972 ms |
98320 KB |
Output is correct |
| 9 |
Correct |
860 ms |
98332 KB |
Output is correct |
| 10 |
Correct |
860 ms |
98320 KB |
Output is correct |
| 11 |
Correct |
904 ms |
98320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
98188 KB |
Output is correct |
| 2 |
Correct |
1492 ms |
116800 KB |
Output is correct |
| 3 |
Correct |
1864 ms |
117964 KB |
Output is correct |
| 4 |
Correct |
1108 ms |
117864 KB |
Output is correct |
| 5 |
Correct |
1780 ms |
127060 KB |
Output is correct |
| 6 |
Correct |
1984 ms |
117756 KB |
Output is correct |
| 7 |
Correct |
1532 ms |
101964 KB |
Output is correct |
| 8 |
Correct |
1008 ms |
102252 KB |
Output is correct |
| 9 |
Correct |
1260 ms |
102724 KB |
Output is correct |
| 10 |
Correct |
1516 ms |
101916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2096 ms |
116800 KB |
Output is correct |
| 2 |
Correct |
2236 ms |
116800 KB |
Output is correct |
| 3 |
Correct |
2016 ms |
117476 KB |
Output is correct |
| 4 |
Correct |
2252 ms |
117764 KB |
Output is correct |
| 5 |
Correct |
2624 ms |
117692 KB |
Output is correct |
| 6 |
Correct |
2308 ms |
124172 KB |
Output is correct |
| 7 |
Correct |
1864 ms |
117864 KB |
Output is correct |
| 8 |
Correct |
2776 ms |
117508 KB |
Output is correct |
| 9 |
Correct |
2772 ms |
117244 KB |
Output is correct |
| 10 |
Correct |
2748 ms |
117528 KB |
Output is correct |
| 11 |
Correct |
1276 ms |
102968 KB |
Output is correct |
| 12 |
Correct |
1064 ms |
102252 KB |
Output is correct |
| 13 |
Correct |
1448 ms |
101884 KB |
Output is correct |
| 14 |
Correct |
1444 ms |
101884 KB |
Output is correct |
| 15 |
Correct |
1448 ms |
101916 KB |
Output is correct |
| 16 |
Correct |
1516 ms |
101912 KB |
Output is correct |
