#include <bits/stdc++.h>
#include "factories.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
const int NN = 500001;
const int K = 20;
const ll INF = (ll)1e18;
int mark[NN], s[NN], e[NN], dep[NN], p[NN][K], dfstime;
ll d[NN], ans;
vector <pair <int, ll> > v[NN], g[NN];
void dfs(int node, int pnode){
s[node] = dfstime++;
p[node][0] = pnode;
for(int i = 1 ; i < K ; i++){
p[node][i] = p[p[node][i - 1]][i - 1];
}
for(auto &i : v[node]){
if(i.first == pnode) continue;
d[i.first] = d[node] + i.second;
dep[i.first] = dep[node] + 1;
dfs(i.first, node);
}
e[node] = dfstime - 1;
}
bool inside(int x, int y){
return s[x] <= s[y] && e[y] <= e[x];
}
int lift(int x, int k){
for(int i = 0 ; i < K ; i++){
if((k >> i) & 1){
x = p[x][i];
}
}
return x;
}
int LCA(int x, int y){
if(dep[x] >= dep[y]) swap(x, y);
y = lift(y, dep[y] - dep[x]);
if(x == y) return x;
for(int i = K - 1 ; i >= 0 ; i--){
if(p[x][i] != p[y][i]){
x = p[x][i];
y = p[y][i];
}
}
return p[x][0];
}
pair <ll, ll> solve(int node, int pnode){
pair <ll, ll> cur = make_pair(INF, INF);
if(mark[node] == 1) cur.first = 0;
if(mark[node] == 2) cur.second = 0;
for(auto &i : g[node]){
if(i.first == pnode) continue;
auto f = solve(i.first, node);
f.first += i.second;
f.second += i.second;
ans = min(ans, cur.first + f.second);
ans = min(ans, cur.second + f.first);
cur.first = min(cur.first, f.first);
cur.second = min(cur.second, f.second);
}
return cur;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0 ; i < N - 1 ; i++){
v[A[i]].push_back(make_pair(B[i], D[i]));
v[B[i]].push_back(make_pair(A[i], D[i]));
}
dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector <int> all;
for(int i = 0 ; i < S ; i++){
mark[X[i]] = 1;
all.push_back(X[i]);
}
for(int i = 0 ; i < T ; i++){
mark[Y[i]] = 2;
all.push_back(Y[i]);
}
sort(all.begin(), all.end(), [&](int l, int r){
return s[l] < s[r];
});
int all_sz = all.size();
for(int i = 0 ; i < all_sz ; i++){
all.push_back(LCA(all[i], all[(i + 1) % all_sz]));
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
sort(all.begin(), all.end(), [&](int l, int r){
return s[l] < s[r];
});
vector <int> cur;
for(auto &i : all){
while(cur.size() && !inside(cur.back(), i)) cur.pop_back();
if(cur.size()){
ll cost = d[i] - d[cur.back()];
g[cur.back()].push_back(make_pair(i, cost));
g[i].push_back(make_pair(cur.back(), cost));
}
cur.push_back(i);
}
ans = INF;
solve(all[0], 0);
for(auto &i : all){
g[i].clear();
mark[i] = 0;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
24140 KB |
Output is correct |
2 |
Correct |
1139 ms |
33024 KB |
Output is correct |
3 |
Correct |
1165 ms |
32988 KB |
Output is correct |
4 |
Correct |
1127 ms |
33220 KB |
Output is correct |
5 |
Correct |
968 ms |
33132 KB |
Output is correct |
6 |
Correct |
920 ms |
32956 KB |
Output is correct |
7 |
Correct |
1173 ms |
32888 KB |
Output is correct |
8 |
Correct |
1123 ms |
33120 KB |
Output is correct |
9 |
Correct |
963 ms |
33204 KB |
Output is correct |
10 |
Correct |
889 ms |
32840 KB |
Output is correct |
11 |
Correct |
1183 ms |
33040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
24032 KB |
Output is correct |
2 |
Correct |
2073 ms |
127440 KB |
Output is correct |
3 |
Correct |
2512 ms |
148328 KB |
Output is correct |
4 |
Correct |
1459 ms |
142992 KB |
Output is correct |
5 |
Correct |
2801 ms |
178244 KB |
Output is correct |
6 |
Correct |
2866 ms |
150752 KB |
Output is correct |
7 |
Correct |
2343 ms |
67700 KB |
Output is correct |
8 |
Correct |
1329 ms |
67248 KB |
Output is correct |
9 |
Correct |
2375 ms |
72960 KB |
Output is correct |
10 |
Correct |
2245 ms |
69156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
24140 KB |
Output is correct |
2 |
Correct |
1139 ms |
33024 KB |
Output is correct |
3 |
Correct |
1165 ms |
32988 KB |
Output is correct |
4 |
Correct |
1127 ms |
33220 KB |
Output is correct |
5 |
Correct |
968 ms |
33132 KB |
Output is correct |
6 |
Correct |
920 ms |
32956 KB |
Output is correct |
7 |
Correct |
1173 ms |
32888 KB |
Output is correct |
8 |
Correct |
1123 ms |
33120 KB |
Output is correct |
9 |
Correct |
963 ms |
33204 KB |
Output is correct |
10 |
Correct |
889 ms |
32840 KB |
Output is correct |
11 |
Correct |
1183 ms |
33040 KB |
Output is correct |
12 |
Correct |
16 ms |
24032 KB |
Output is correct |
13 |
Correct |
2073 ms |
127440 KB |
Output is correct |
14 |
Correct |
2512 ms |
148328 KB |
Output is correct |
15 |
Correct |
1459 ms |
142992 KB |
Output is correct |
16 |
Correct |
2801 ms |
178244 KB |
Output is correct |
17 |
Correct |
2866 ms |
150752 KB |
Output is correct |
18 |
Correct |
2343 ms |
67700 KB |
Output is correct |
19 |
Correct |
1329 ms |
67248 KB |
Output is correct |
20 |
Correct |
2375 ms |
72960 KB |
Output is correct |
21 |
Correct |
2245 ms |
69156 KB |
Output is correct |
22 |
Correct |
3404 ms |
162008 KB |
Output is correct |
23 |
Correct |
3274 ms |
162732 KB |
Output is correct |
24 |
Correct |
3757 ms |
165964 KB |
Output is correct |
25 |
Correct |
3943 ms |
169068 KB |
Output is correct |
26 |
Correct |
4040 ms |
160416 KB |
Output is correct |
27 |
Correct |
3697 ms |
186928 KB |
Output is correct |
28 |
Correct |
2661 ms |
157212 KB |
Output is correct |
29 |
Correct |
4725 ms |
159152 KB |
Output is correct |
30 |
Correct |
4673 ms |
158628 KB |
Output is correct |
31 |
Correct |
4583 ms |
159064 KB |
Output is correct |
32 |
Correct |
2177 ms |
75488 KB |
Output is correct |
33 |
Correct |
1540 ms |
69900 KB |
Output is correct |
34 |
Correct |
2284 ms |
66876 KB |
Output is correct |
35 |
Correct |
2132 ms |
66440 KB |
Output is correct |
36 |
Correct |
2542 ms |
67336 KB |
Output is correct |
37 |
Correct |
2476 ms |
67164 KB |
Output is correct |