#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;
const int OFF=(1<<19);
struct Tournament{
ll tour[2*OFF];
Tournament() {
fill(tour, tour+2*OFF, MAX);
}
ll query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
if (lo>=a && hi<=b) return tour[pos];
if (lo>=b || hi<=a) return MAX;
int mid=(lo+hi)/2;
return min(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
}
void update(int pos, ll val) {
pos+=OFF; tour[pos]=val;
pos/=2;
while (pos) {
tour[pos]=min(tour[pos*2], tour[pos*2+1]);
pos/=2;
}
}
};
int n, dtime=0;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN], L[MAXN], R[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];
vector <int> v;
int cmp(int a, int b) {
return L[a]<L[b];
}
void dfs(int node, int rod, ll d) {
par[0][node]=rod;
dist[node]=d;
dep[node]=dep[rod]+1;
L[node]=dtime++;
// 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);
R[node]=dtime;
}
void build() {
for (int i=1; i<LOG; ++i) {
for (int j=0; j<n; ++j) {
par[i][j]=par[i-1][par[i-1][j]];
}
}
}
int lca(int x, int y) {
if (dep[x]<dep[y]) swap(x, y);
for (int i=LOG-1; i>=0; --i) {
if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
}
if (x==y) return x;
for (int i=LOG-1; i>=0; --i) {
if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
}
return par[0][x];
}
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);
build();
}
Tournament TA, TB;
long long Query(int S, int x[], int T, int y[]) {
v.clear();
for (int i=0; i<S; ++i) {
v.pb(x[i]);
TA.update(L[x[i]], dist[x[i]]);
}
for (int i=0; i<T; ++i) {
v.pb(y[i]);
TB.update(L[y[i]], dist[y[i]]);
}
sort(v.begin(), v.end(), cmp);
ll sol=MAX;
for (int i=1; i<(int)v.size(); ++i) {
int lc=lca(v[i-1], v[i]);
ll curr=TA.query(L[lc], R[lc])+TB.query(L[lc], R[lc])-dist[lc]*2;
sol=min(sol, curr);
}
for (int i=0; i<S; ++i) TA.update(L[x[i]], MAX);
for (int i=0; i<T; ++i) TB.update(L[y[i]], MAX);
return sol;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
29292 KB |
Output is correct |
2 |
Correct |
1938 ms |
47172 KB |
Output is correct |
3 |
Correct |
2137 ms |
46956 KB |
Output is correct |
4 |
Correct |
2005 ms |
47032 KB |
Output is correct |
5 |
Correct |
1965 ms |
47212 KB |
Output is correct |
6 |
Correct |
2021 ms |
47012 KB |
Output is correct |
7 |
Correct |
2138 ms |
47092 KB |
Output is correct |
8 |
Correct |
2004 ms |
47084 KB |
Output is correct |
9 |
Correct |
1976 ms |
47228 KB |
Output is correct |
10 |
Correct |
2013 ms |
46960 KB |
Output is correct |
11 |
Correct |
2144 ms |
47348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
28908 KB |
Output is correct |
2 |
Correct |
3387 ms |
124516 KB |
Output is correct |
3 |
Correct |
5014 ms |
128596 KB |
Output is correct |
4 |
Correct |
2444 ms |
127060 KB |
Output is correct |
5 |
Correct |
4177 ms |
148712 KB |
Output is correct |
6 |
Correct |
5405 ms |
127496 KB |
Output is correct |
7 |
Correct |
6453 ms |
62528 KB |
Output is correct |
8 |
Correct |
3570 ms |
67804 KB |
Output is correct |
9 |
Correct |
4847 ms |
70688 KB |
Output is correct |
10 |
Correct |
6267 ms |
68412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
29292 KB |
Output is correct |
2 |
Correct |
1938 ms |
47172 KB |
Output is correct |
3 |
Correct |
2137 ms |
46956 KB |
Output is correct |
4 |
Correct |
2005 ms |
47032 KB |
Output is correct |
5 |
Correct |
1965 ms |
47212 KB |
Output is correct |
6 |
Correct |
2021 ms |
47012 KB |
Output is correct |
7 |
Correct |
2138 ms |
47092 KB |
Output is correct |
8 |
Correct |
2004 ms |
47084 KB |
Output is correct |
9 |
Correct |
1976 ms |
47228 KB |
Output is correct |
10 |
Correct |
2013 ms |
46960 KB |
Output is correct |
11 |
Correct |
2144 ms |
47348 KB |
Output is correct |
12 |
Correct |
23 ms |
28908 KB |
Output is correct |
13 |
Correct |
3387 ms |
124516 KB |
Output is correct |
14 |
Correct |
5014 ms |
128596 KB |
Output is correct |
15 |
Correct |
2444 ms |
127060 KB |
Output is correct |
16 |
Correct |
4177 ms |
148712 KB |
Output is correct |
17 |
Correct |
5405 ms |
127496 KB |
Output is correct |
18 |
Correct |
6453 ms |
62528 KB |
Output is correct |
19 |
Correct |
3570 ms |
67804 KB |
Output is correct |
20 |
Correct |
4847 ms |
70688 KB |
Output is correct |
21 |
Correct |
6267 ms |
68412 KB |
Output is correct |
22 |
Correct |
5600 ms |
118804 KB |
Output is correct |
23 |
Correct |
6191 ms |
121228 KB |
Output is correct |
24 |
Correct |
6093 ms |
121068 KB |
Output is correct |
25 |
Correct |
6414 ms |
124236 KB |
Output is correct |
26 |
Execution timed out |
8074 ms |
120524 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |