#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pii pair<int, ll>
const int ar = 5e5 + 5;
const ll inf = 1e15;
int n, q, N, A[ar], B[ar], D[ar], Y[ar], X[ar], S, T;
int sz[ar], vt[ar];
vector<pii> adj[ar], ancestors[ar];
bool deleted[ar];
ll dp[ar];
void dfs(int u, int par) {
++N;
sz[u] = 1;
for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) {
dfs(x, u);
sz[u] += sz[x];
}
}
int find_centroid(int u, int par) {
for(auto [x, w] : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
return u;
}
void build_distance(int u, int par, int c, ll d) {
ancestors[u].emplace_back(c, d);
for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + w);
}
void build_tree(int u) {
N = 0;
dfs(u, u);
int centroid = find_centroid(u, u);
deleted[centroid] = 1;
build_distance(centroid, centroid, centroid, 0);
for(auto [x, w] : adj[centroid]) {
if(!deleted[x]) build_tree(x);
}
}
void add(int u) {
for(auto [x, w] : ancestors[u]) dp[x] = w;
}
void del(int u) {
for(auto [x, w] : ancestors[u]) dp[x] = inf;
}
ll get(int u) {
ll ans = inf;
for(auto [x, w] : ancestors[u]) {
ans = min(ans, w + dp[x]);
}
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; ++i) {
A[i]++; B[i]++;
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
for(int i = 1; i <= N; ++i) dp[i] = inf;
build_tree(1);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++)
add(X[i] + 1);
ll ans = 1e15;
for (int i = 0; i < T; i++)
ans = min(ans, get(Y[i] + 1));
for (int i = 0; i < S; i++)
del(X[i] + 1);
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) {
| ^
factories.cpp: In function 'int find_centroid(int, int)':
factories.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | for(auto [x, w] : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
| ^
factories.cpp: In function 'void build_distance(int, int, int, long long int)':
factories.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + w);
| ^
factories.cpp: In function 'void build_tree(int)':
factories.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto [x, w] : adj[centroid]) {
| ^
factories.cpp: In function 'void add(int)':
factories.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for(auto [x, w] : ancestors[u]) dp[x] = w;
| ^
factories.cpp: In function 'void del(int)':
factories.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | for(auto [x, w] : ancestors[u]) dp[x] = inf;
| ^
factories.cpp: In function 'long long int get(int)':
factories.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for(auto [x, w] : ancestors[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
45660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
45912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
45660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
