#include <bits/stdc++.h>
#include "factories.h"
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 5e5 + 5;
const double eps = 1e-9;
int n, del[maxn], sub[maxn];
ll dist[maxn];
vector<vector<pll> > graph(maxn), anc(maxn);
int get_sub(int u, int p) {
sub[u] = 1;
for(auto &[v, _] : graph[u]) {
if(v == p || del[v]) continue;
sub[u] += get_sub(v, u);
}
return sub[u];
}
int get_cen(int u, int p, int sz) {
for(auto &[v, _] : graph[u]) {
if(v == p || del[v]) continue;
if(2 * sub[v] > sz) return get_cen(v, u, sz);
}
return u;
}
void get_dist(int u, int cen, int p, ll d) {
for(auto &[v, w] : graph[u]) {
if(v == p || del[v]) continue;
get_dist(v, cen, u, d + w);
}
anc[u].push_back({ cen, d });
}
void update(int u, int t) {
for(auto &[v, d] : anc[u]) {
if(t) dist[v] = min(dist[v], d);
else dist[v] = 1e18;
}
dist[u] = (t ? 0 : 1e18);
}
ll query(int u) {
ll ans = dist[u];
for(auto &[v, d] : anc[u])
ans = min(ans, d + dist[v]);
return ans;
}
void build(int u) {
int cen = get_cen(u, -1, get_sub(u, -1));
for(auto &[v, w] : graph[u]) {
if(del[v]) continue;
get_dist(v, cen, cen, w);
}
del[cen] = 1;
for(auto &[v, w] : graph[u]) {
if(del[v]) continue;
build(v);
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<n-1; i++) {
graph[A[i]].push_back({ B[i], D[i] });
graph[B[i]].push_back({ A[i], D[i] });
}
for(int i=0; i<n; i++) dist[i] = 1e18;
build(0);
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = 1e18;
for(int i=0; i<S; i++) update(X[i], 1);
for(int i=0; i<T; i++) ans = min(ans, query(Y[i]));
for(int i=0; i<S; i++) update(X[i], 0);
return ans;
}
Compilation message
factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto &[v, _] : graph[u]) {
| ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:35:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for(auto &[v, _] : graph[u]) {
| ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
43 | for(auto &[v, w] : graph[u]) {
| ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto &[v, d] : anc[u]) {
| ^
factories.cpp: In function 'll query(int)':
factories.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for(auto &[v, d] : anc[u])
| ^
factories.cpp: In function 'void build(int)':
factories.cpp:68:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for(auto &[v, w] : graph[u]) {
| ^
factories.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | for(auto &[v, w] : graph[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
46680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
46428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
46680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
