#include <bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define pb push_back
#define INF 1e18
using namespace std;
const int maxN = 500050;
const int L = log2(maxN) + 10;
vector<pll> adj[maxN];
set<ll> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], dist[maxN][L], root, lvl[maxN], P[maxN][L], updist[maxN][L];
void dfs2(int a, int prt, ll cur) {
lvl[a] = lvl[prt]+1;
P[a][0] = prt;
updist[a][0] = cur;
for (int i = 1; i < L; ++i) {
P[a][i] = P[P[a][i-1]][i-1];
updist[a][i] = updist[P[a][i-1]][i] + updist[a][i-1];
}
for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
}
long long lca(int a, int b) {
if (lvl[a] < lvl[b]) swap(a, b);
int j = lvl[a] - lvl[b];
ll dis = 0;
for (int i = 0; i < L; ++i) {
if (j & (1<<i)) {
dis += updist[a][i];
a = P[a][i];
}
}
if (a==b) return dis;
for (int i = L-1; i >= 0; --i) {
if (P[a][i] != P[b][i]) {
dis += (updist[a][i] + updist[b][i]);
a = P[a][i]; b = P[b][i];
}
}
return dis + updist[a][0] + updist[b][0];
}
void computedist(int n) {
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = i; j != -1; j = up[j]) {
dist[i][cnt++] = lca(i, j);
}
}
}
int dfs(int i, int prt=-1) {
sz[i] = 1;
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
sz[i] += dfs(j, i);
}
return sz[i];
}
int find_centroid(int i, int m, int prt=-1) {
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
if (sz[j] > m/2) return find_centroid(j, m, i);
}
return i;
}
int decom(int x=0) {
int cen = find_centroid(x, dfs(x));
mark[cen] = 1;
root = cen;
for (auto [j, w] : adj[cen]) {
if (mark[j]) continue;
int c = decom(j);
up[c] = cen;
}
return cen;
}
void update(int v) {
int cur = v, cnt = 0;
while (cur != -1) {
s.insert(cur);
mn[cur] = min(mn[cur], dist[v][cnt]);
cur = up[cur];
cnt++;
}
}
ll query(int v) {
ll ans = INF, cur = v, cnt = 0;
while (cur != -1) {
ans = min(ans, mn[cur] + dist[v][cnt]);
cur = up[cur];
cnt++;
}
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; ++i) {
adj[A[i]].pb({B[i], D[i]});
adj[B[i]].pb({A[i], D[i]});
}
for (int i = 0; i < N; ++i) mn[i] = INF;
memset(up, -1, sizeof(up));
decom();
dfs2(0, -1, 0);
computedist(N);
}
ll Query(int S, int X[], int T, int Y[]) {
s.clear();
for (int i = 0; i < S; ++i) update(X[i]);
ll ans = INF;
for (int i = 0; i < T; ++i) ans = min(ans, query(Y[i]));
for (auto i : s) mn[i] = INF;
return ans;
}
Compilation message
factories.cpp: In function 'void dfs2(int, int, long long int)':
factories.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
| ^
factories.cpp: In function 'int dfs(int, int)':
factories.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for (auto [j, w] : adj[i]) {
| ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for (auto [j, w] : adj[i]) {
| ^
factories.cpp: In function 'int decom(int)':
factories.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for (auto [j, w] : adj[cen]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
