//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e18 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, q;
vector<pii> adj[nmax];
int h[nmax], up[nmax][lg + 1];
ll d[nmax];
void dfs_1(int u, int p){
for(auto [w, v] : adj[u]){
if(v == p) continue;
h[v] = h[u] + 1;
up[v][0] = u;
d[v] = d[u] + w;
for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
dfs_1(v, u);
}
}
int lca(int u, int v){
if(h[u] != h[v]){
if(h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for(int j = 0; j <= __lg(k); ++j){
if(k >> j & 1) u = up[u][j];
}
}
if(u == v) return u;
for(int j = __lg(h[u]); j >=0;--j){
if(up[u][j] != up[v][j]){
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
ll dist(int u, int v){
return d[u] + d[v] - 2 * d[lca(u, v)];
}
bool vis[nmax];
int sz[nmax], par[nmax];
void dfs_2(int u, int p){
sz[u] = 1;
for(auto [w, v] : adj[u]){
if(v == p || vis[v]) continue;
dfs_2(v, u);
sz[u] += sz[v];
}
}
int cntw = 0;
int Find(int u, int p){
for(auto [w,v] : adj[u]){
if(v == p || vis[v]) continue;
if(sz[v] > cntw / 2) return Find(v, u);
}
return u;
}
int centroid(int u){
dfs_2(u, -1); cntw = sz[u];
int root = Find(u, -1);
vis[root] = 1;
for(auto [w, v] : adj[root]){
if(vis[v]) continue;
int x = centroid(v);
par[x] = root;
}
return root;
}
vector<int> rev;
ll dp[nmax];
void update(int u){
int x = u;
while(u > 0){
dp[u] = min(dp[u], dist(u, x));
rev.push_back(u);
u = par[u];
}
}
ll get(int u){
int x = u;
ll res = oo;
while(u > 0){
res = min(res, dp[u] + dist(u, x));
u = par[u];
}
return res;
}
int X[nmax], Y[nmax], S, T;
void Init(int n, int A[], int B[], int D[]){
for(int i = 0; i < n - 1; ++i){
int u, v, w;
u = A[i], v = B[i], w = D[i];
++u, ++v;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
dfs_1(1, -1);
centroid(1);
memset(dp, 0x3f, sizeof dp);
}
ll Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; ++i) ++X[i];
for(int i = 0; i < T; ++i) ++Y[i];
for(int i = 0; i < S; ++i) update(X[i]);
ll ans = oo;
for(int i = 0; i < T; ++i){
ans = min(ans,get(Y[i]));
}
cout << ans << endl;
for(auto p : rev)dp[p] = oo;
}
/*
*/
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:127:1: warning: no return statement in function returning non-void [-Wreturn-type]
127 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
46684 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
46428 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
46684 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
