#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;
vector<pll> adj[maxN];
map<pll, ll> mp;
set<ll> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], dist[maxN], updist[maxN];
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;
}
void dfs2(int i, ll cur=0, int prt=-1) {
dist[i] = cur;
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
dfs2(j, cur+w, i);
}
}
int decom(int x=0) {
int cen = find_centroid(x, dfs(x));
mark[cen] = 1;
vector<int> v;
for (auto [j, w] : adj[cen]) {
if (mark[j]) continue;
int c = decom(j);
up[c] = cen;
v.pb(c);
}
dfs2(cen);
for (int i = 0; i < v.size(); ++i) updist[v[i]] = dist[v[i]];
mark[cen] = 0;
return cen;
}
void update(int v) {
int cur = v;
ll dis = 0;
while (cur != -1) {
s.insert(cur);
mn[cur] = min(mn[cur], dis);
dis += updist[cur];
cur = up[cur];
}
}
ll query(int v) {
ll ans = INF, cur = v, dis = 0;
while (cur != -1) {
ans = min(ans, mn[cur] + dis);
dis += updist[cur];
cur = up[cur];
}
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();
}
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 'int dfs(int, int)':
factories.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
23 | for (auto [j, w] : adj[i]) {
| ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | for (auto [j, w] : adj[i]) {
| ^
factories.cpp: In function 'void dfs2(int, long long int, int)':
factories.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for (auto [j, w] : adj[i]) {
| ^
factories.cpp: In function 'int decom(int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for (auto [j, w] : adj[cen]) {
| ^
factories.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0; i < v.size(); ++i) updist[v[i]] = dist[v[i]];
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
16212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
16212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
