#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;
const long long maxn = 500001, INF = LLONG_MAX / 3;
bool rem[maxn];
int sub_sz[maxn];
long long mini[maxn];
vector <pair<int, long long> > Dist[maxn];
vector <pii > G [maxn];
int dfs(int u, int p = -1){
sub_sz[u] = 1;
for(auto [v, d] : G[u]){
if(v != p && !rem[v]){
sub_sz[u] += dfs(v, u);
}
}
return sub_sz[u];
}
void dfs2(int u, int p, long long dist, int r){
Dist[u].push_back({r, dist});
for(auto [v, d] : G[u]){
if(v != p && !rem[v]){
dfs2(v, u, dist + d, r);
}
}
}
int g_cen(int u, int sz, int p = -1){
for(auto [v, d] : G[u]){
if(v != p && !rem[v]){
if(sub_sz[v] * 2 > sz){
return g_cen(v, sz, u);
}
}
}
return u;
}
int sol(int r = 0){
int sz = dfs(r);
int c = g_cen(r, sz);
dfs2(c, -1, 0, c);
rem[c] = 1;
for(auto [v, d] : G[c]){
if(!rem[v]){
sol(v);
}
}
return c;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++){
int a = A[i], b = B[i], d = D[i];
G[a].push_back({b, d});
G[b].push_back({a, d});
}
for(int i = 0; i < N - 1; i++) {mini[i] = INF;}
sol();
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans = INF;
vector <int> q;
for(int i = 0; i < S; i++){
int x = X[i];
for(auto [v, d] : Dist[x]){
mini[v] = min(mini[v], d);
q.push_back(v);
}
}
for(int i = 0; i < T; i++){
int y = Y[i];
for(auto [v, d] : Dist[y]){
ans = min(ans, mini[v] + d);
}
}//*/
for(auto x : q) {mini[x] = INF;}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
25436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
25436 KB |
Output is correct |
| 2 |
Incorrect |
1446 ms |
193508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
25436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
