#include "factories.h"
#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
const int N = 5e5 + 10;
const LL INF = (LL)1e18;
const int LG = 19;
int n, s, t, q, timer;
int a[N], b[N], e[N], h[N];
LL f[N], d[N][LG + 3];
vector <II> adj[N];
struct CD {
int cPar[N], c[N];
void Init() {
memset(cPar, -1, sizeof cPar);
memset(d, -1, sizeof d);
DFS(1);
Centroid(1, -1, c[1], -2);
}
void DFS(int u, int par = -1) {
c[u] = 1;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
DFS(v, u);
c[u] += c[v];
}
}
void DFS(int u, int par, int cen) {
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == par || cPar[v] != -1) continue;
d[v][h[cen]] = d[u][h[cen]] + w;
DFS(v, u, cen);
}
}
void Centroid(int u, int par, int sz, int preC) {
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
if (c[v] * 2 > sz) {
Centroid(v, u, sz, preC);
return;
}
}
cPar[u] = preC;
if (preC != -2) h[u] = h[preC] + 1;
else h[u] = 1;
d[u][h[u]] = 0;
DFS(u, -1, u);
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (cPar[v] != -1) continue;
DFS(v);
Centroid(v, u, c[v], u);
}
}
} CD;
void Init(int NN, int A[], int B[], int D[]) {
n = NN;
REP(i, 0, n - 1) {
int u = A[i], v = B[i], w = D[i];
++u; ++v;
adj[u].push_back(II(v, w));
adj[v].push_back(II(u, w));
}
FOR(i, 1, n) f[i] = INF;
CD.Init();
}
void Update(int u) {
int x = u;
while (x != -2) {
assert(d[u][h[x]] != -1);
f[x] = min(f[x], d[u][h[x]]);
x = CD.cPar[x];
}
}
void Assign(int u, LL v) {
int x = u;
while (x != -2) {
f[x] = v;
x = CD.cPar[x];
}
}
LL Query(int u) {
int x = u; LL ans = INF;
while (x != -2) {
assert(d[u][h[x]] != -1);
ans = min(ans, f[x] + d[u][h[x]]);
x = CD.cPar[x];
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
s = S; t = T;
LL ans = INF;
REP(i, 0, s) {
++X[i];
Update(X[i]);
}
REP(i, 0, t) {
++Y[i];
ans = min(ans, Query(Y[i]));
}
REP(i, 0, s) Assign(X[i], INF);
return ans;
}
Compilation message
factories.cpp: In member function 'void CD::DFS(int, int)':
factories.cpp:6:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:37:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp: In member function 'void CD::DFS(int, int, int)':
factories.cpp:6:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:44:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp: In member function 'void CD::Centroid(int, int, int, int)':
factories.cpp:6:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:52:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp:6:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:64:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
100472 KB |
Output is correct |
| 2 |
Correct |
465 ms |
108720 KB |
Output is correct |
| 3 |
Correct |
482 ms |
108720 KB |
Output is correct |
| 4 |
Correct |
490 ms |
108724 KB |
Output is correct |
| 5 |
Correct |
504 ms |
108972 KB |
Output is correct |
| 6 |
Correct |
385 ms |
108972 KB |
Output is correct |
| 7 |
Correct |
487 ms |
108972 KB |
Output is correct |
| 8 |
Correct |
494 ms |
108972 KB |
Output is correct |
| 9 |
Correct |
534 ms |
108996 KB |
Output is correct |
| 10 |
Correct |
390 ms |
108996 KB |
Output is correct |
| 11 |
Correct |
495 ms |
108996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
108996 KB |
Output is correct |
| 2 |
Correct |
2452 ms |
139760 KB |
Output is correct |
| 3 |
Correct |
3542 ms |
139788 KB |
Output is correct |
| 4 |
Correct |
1083 ms |
140812 KB |
Output is correct |
| 5 |
Correct |
4696 ms |
151252 KB |
Output is correct |
| 6 |
Correct |
3721 ms |
151252 KB |
Output is correct |
| 7 |
Correct |
1189 ms |
151252 KB |
Output is correct |
| 8 |
Correct |
600 ms |
151252 KB |
Output is correct |
| 9 |
Correct |
1424 ms |
151252 KB |
Output is correct |
| 10 |
Correct |
1223 ms |
151252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2793 ms |
151252 KB |
Output is correct |
| 2 |
Correct |
3159 ms |
151252 KB |
Output is correct |
| 3 |
Correct |
4387 ms |
151252 KB |
Output is correct |
| 4 |
Correct |
4325 ms |
169996 KB |
Output is correct |
| 5 |
Correct |
4062 ms |
190988 KB |
Output is correct |
| 6 |
Correct |
4809 ms |
225968 KB |
Output is correct |
| 7 |
Correct |
1283 ms |
242792 KB |
Output is correct |
| 8 |
Correct |
3821 ms |
264376 KB |
Output is correct |
| 9 |
Correct |
4026 ms |
288616 KB |
Output is correct |
| 10 |
Correct |
4035 ms |
313232 KB |
Output is correct |
| 11 |
Correct |
1362 ms |
313232 KB |
Output is correct |
| 12 |
Correct |
591 ms |
317056 KB |
Output is correct |
| 13 |
Correct |
943 ms |
327824 KB |
Output is correct |
| 14 |
Correct |
901 ms |
341252 KB |
Output is correct |
| 15 |
Correct |
1119 ms |
355060 KB |
Output is correct |
| 16 |
Correct |
1149 ms |
368468 KB |
Output is correct |
