#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
const int N = 500002,L=20;
int n;
vector<pair<int,int>> adj[N];
int tin[N],tout[N],timer,up[N][L];
ll dis[N][L];
bool there[N],there1[N];
ll diss[N],diss1[N] , best[N],best1[N];
void dfs(int node , int par , int di){
tin[node] = timer++;
up[node][0] = par;
dis[node][0] = di;
for(int i = 1; i < L; i++){
up[node][i] = up[up[node][i-1]][i-1];
dis[node][i] = dis[node][i-1] + dis[up[node][i-1]][i-1];
}
for(auto i : adj[node]){
if(i.vf != par){
dfs(i.vf , node , i.vs);
}
}
tout[node] = timer++;
}
bool is_lca(int x , int y){
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int find(int x , int y){
if(is_lca(x,y))return x;
if(is_lca(y,x))return y;
for(int i = L - 1; i >= 0; i--){
if(!is_lca(up[x][i] , y))x = up[x][i];
}
return up[x][0];
}
void Init(int nn, int A[], int B[], int D[]) {
n = nn;
for(int i = 0; i < n-1; i++){
adj[A[i]].pb(mp(B[i],D[i]));
adj[B[i]].pb(mp(A[i],D[i]));
}
memset(there,0,sizeof there);
memset(there1,0,sizeof there1);
timer = 0;
dfs(0,0,0);
}
ll cal(int x , int y){
if(x == y)return 0;
ll ans = 0;
for(int i = L - 1; i >= 0; i--){
if(!is_lca(up[x][i] , y)){
ans += dis[x][i];
x = up[x][i];
}
}
ans += dis[x][0];
return ans;
}
ll brute(int a , int x[] , int b , int y[]){
ll ans = 1e18;
for(int i = 0; i < a; i++){
for(int j = 0; j < b; j++){
int lca = find(x[i] , y[j]);
//cout << x[i] << ' ' << y[j] << ' ' << lca << ' ' << cal(x[i] , lca) << ' ' << cal(y[i] , lca) << '\n';
ans = min(ans , cal(x[i] , lca) + cal(y[j] , lca));
}
}
return ans;
}
void dfs1(int node , int par){
best[node] = best1[node] = diss[node] = diss1[node] = 1e18;
if(there[node])best[node] = diss[node] = 0;
if(there1[node])best1[node] = diss1[node] = 0;
if(there[node] && there1[node]){
cout << "came " << node << '\n';
}
for(auto i : adj[node]){
if(i.vf != par){
dfs1(i.vf , node);
ll di = best[i.vf] + i.vs;
if(best[node] > di){
diss[node] = best[node];
best[node] = di;
}
else {
diss[node] = min(diss[node] , di);
}
di = best1[i.vf] + i.vs;
if(best1[node] > di){
diss1[node] = best1[node];
best1[node] = di;
}
else diss1[node] = min(diss1[node] , di);
}
}
}
void dfs2(int node , int par , ll di , ll di1){
best[node] = min(best[node] , di);
best1[node] = min(best1[node] , di1);
diss[node] = min(diss[node], di);
diss1[node] = min(diss1[node] , di1);
for(auto i : adj[node]){
if(i.vf != par){
ll d = i.vs;
ll d1 = i.vs;
if(best[node] == best[i.vf] + i.vs)d += diss[node];
else d += best[node];
if(best1[node] == best1[i.vf] + i.vs)d1 += diss1[node];
else d1 += best1[node];
dfs2(i.vf , node , d, d1);
}
}
}
ll full(int a , int x[] , int b , int y[]){
for(int i = 0; i < a; i++)there[x[i]] = 1;
for(int i = 0; i < b; i++)there1[y[i]] = 1;
dfs1(0 , 0);
dfs2(0,0,1e18,1e18);
ll res = 1e18;
for(int i = 0; i < n; i++){
res = min(res , best[i] + best1[i]);
//cout << best[i] << ' ' << best1[i] << '\n';
}
for(int i = 0; i < a; i++)there[x[i]] = 0;
for(int i = 0; i < b; i++)there1[y[i]] = 0;
return res;
}
long long Query(int a, int x[], int b, int y[]) {
if(a*b <= n)return brute(a,x,b,y);
return full(a,x,b,y);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
13696 KB |
Output is correct |
2 |
Correct |
627 ms |
32068 KB |
Output is correct |
3 |
Correct |
1869 ms |
32360 KB |
Output is correct |
4 |
Correct |
805 ms |
32336 KB |
Output is correct |
5 |
Correct |
694 ms |
32424 KB |
Output is correct |
6 |
Correct |
465 ms |
32204 KB |
Output is correct |
7 |
Correct |
1833 ms |
32120 KB |
Output is correct |
8 |
Correct |
834 ms |
32396 KB |
Output is correct |
9 |
Correct |
687 ms |
32436 KB |
Output is correct |
10 |
Correct |
355 ms |
32072 KB |
Output is correct |
11 |
Correct |
1936 ms |
32104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
13268 KB |
Output is correct |
2 |
Correct |
1725 ms |
182544 KB |
Output is correct |
3 |
Correct |
6469 ms |
184352 KB |
Output is correct |
4 |
Correct |
1402 ms |
184060 KB |
Output is correct |
5 |
Correct |
4261 ms |
199144 KB |
Output is correct |
6 |
Correct |
4612 ms |
183732 KB |
Output is correct |
7 |
Execution timed out |
8036 ms |
65216 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
13696 KB |
Output is correct |
2 |
Correct |
627 ms |
32068 KB |
Output is correct |
3 |
Correct |
1869 ms |
32360 KB |
Output is correct |
4 |
Correct |
805 ms |
32336 KB |
Output is correct |
5 |
Correct |
694 ms |
32424 KB |
Output is correct |
6 |
Correct |
465 ms |
32204 KB |
Output is correct |
7 |
Correct |
1833 ms |
32120 KB |
Output is correct |
8 |
Correct |
834 ms |
32396 KB |
Output is correct |
9 |
Correct |
687 ms |
32436 KB |
Output is correct |
10 |
Correct |
355 ms |
32072 KB |
Output is correct |
11 |
Correct |
1936 ms |
32104 KB |
Output is correct |
12 |
Correct |
12 ms |
13268 KB |
Output is correct |
13 |
Correct |
1725 ms |
182544 KB |
Output is correct |
14 |
Correct |
6469 ms |
184352 KB |
Output is correct |
15 |
Correct |
1402 ms |
184060 KB |
Output is correct |
16 |
Correct |
4261 ms |
199144 KB |
Output is correct |
17 |
Correct |
4612 ms |
183732 KB |
Output is correct |
18 |
Execution timed out |
8036 ms |
65216 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |