#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long
using namespace std;
const ll INF = 1e18;
const int MAXN = (int)5e5 + 5;
const int MAXQ = (int)1e5 + 5;
const int L = 20;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int get_rand() {
ll x = rnd();
x %= (ll)1e9;
if (x < 0) {
x = -x;
}
return x;
}
int gen(int l, int r) {
return l + (get_rand() % (r - l + 1));
}
vector <pii> g[MAXN];
int n;
int pr[MAXN][L + 1];
ll d[MAXN];
int tin[MAXN], tout[MAXN], tiktak;
bool used[MAXN];
int sub[MAXN];
vector <int> G[MAXN];
pair<int, ll> Gpar[MAXN];
ll opt[MAXN];
void precalc(int v, int par, ll len) {
tin[v] = ++tiktak;
pr[v][0] = par;
d[v] = len;
for (int lv = 1; lv <= L; lv++) {
pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
}
for (auto [to, dist] : g[v]) {
if (to == par) {
continue;
}
precalc(to, v, len + dist);
}
tout[v] = tiktak;
}
bool father(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int get_lca(int a, int b) {
if (father(a, b)) {
return a;
}
if (father(b, a)) {
return b;
}
for (int lv = L; lv >= 0; lv--) {
if (!father(pr[a][lv], b)) {
a = pr[a][lv];
}
}
return pr[a][0];
}
ll get_dist(int a, int b) {
return d[a] + d[b] - (2ll * d[get_lca(a, b)]);
}
void calc(int v, int par) {
sub[v] = 1;
for (auto [to, dist] : g[v]) {
if (to != par && !used[to]) {
calc(to, v);
sub[v] += sub[to];
}
}
}
int find_centroid(int v, int par, int sz) {
for (auto [to, dist] : g[v]) {
if (to != par && sub[to] > sz / 2 && !used[to]) {
return find_centroid(to, v, sz);
}
}
return v;
}
void build(int v, int par) {
calc(v, -1);
int center = find_centroid(v, -1, sub[v]);
used[center] = 1;
if (par != -1) {
G[center].pb(par);
G[par].pb(center);
Gpar[center] = {par, get_dist(center, par)};
}
for (auto [to, dist] : g[center]) {
if (!used[to]) {
build(to, center);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
memset(Gpar, -1, sizeof(Gpar));
fill(opt, opt + MAXN, INF);
n = N;
for (int i = 0; i < n - 1; i++) {
int u = A[i];
int v = B[i];
int dist = D[i];
g[u].pb({v, dist});
g[v].pb({u, dist});
}
precalc(0, 0, 0);
build(0, -1);
}
void upd(int v, int type) {
if (type == 1) {
int cur = v;
ll cur_len = 0;
pair<int, ll> para;
while (1) {
if (cur == -1) {
break;
}
opt[cur] = min(opt[cur], cur_len);
para = Gpar[cur];
cur = para.fr;
cur_len += para.sc;
}
}
else {
int cur = v;
while (1) {
if (cur == -1) {
break;
}
opt[cur] = INF;
cur = Gpar[cur].fr;
}
}
}
ll get(int v) {
ll ret = INF;
int cur = v;
ll cur_len = 0;
pair <int, ll> para;
while (1) {
if (cur == -1) {
break;
}
ret = min(ret, cur_len + opt[cur]);
para = Gpar[cur];
cur = para.fr;
cur_len += para.sc;
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = INF;
for (int i = 0; i < S; i++) {
upd(X[i], 1);
}
for (int i = 0; i < T; i++) {
ans = min(ans, get(Y[i]));
}
for (int i = 0; i < S; i++) {
upd(X[i], -1);
}
return ans;
}
Compilation message
factories.cpp: In function 'void precalc(int, int, long long int)':
factories.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for (auto [to, dist] : g[v]) {
| ^
factories.cpp: In function 'void calc(int, int)':
factories.cpp:89:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for (auto [to, dist] : g[v]) {
| ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:98:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | for (auto [to, dist] : g[v]) {
| ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:116:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
116 | for (auto [to, dist] : g[center]) {
| ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:124:31: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
124 | memset(Gpar, -1, sizeof(Gpar));
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from factories.cpp:6:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, long long int>' declared here
211 | struct pair
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
35908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
35760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
35908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
