#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const int MAX = 5e5 + 10;
vector<int> adj[MAX], cost[MAX];
int lvl[MAX], sub[MAX], p[MAX], vis[MAX];
ll d[20][MAX], ans[MAX];
void calc(int u, int par) { sub[u] = 1;
for(int v : adj[u]) if(v - par && !vis[v])
calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
for(int v : adj[u]) if(v - par && !vis[v])
if(sub[v] > r) return centroid(v, u, r);
return u;
}
void dfs(int l, int u, int par, int pcost) {
if(par + 1) d[l][u] = d[l][par] + pcost;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par || vis[v]) continue;
dfs(l, v, u, c);
}
}
void decompose(int u, int par) {
calc(u, -1);
int c = centroid(u, -1, sub[u] >> 1);
vis[c] = 1, p[c] = par;
if(par + 1) lvl[c] = lvl[par] + 1;
dfs(lvl[c], c, -1, 0);
for(int v : adj[c]) if(v - par && !vis[v])
decompose(v, c);
}
void update(int u) {
for(int v = u; v + 1; v = p[v])
ans[v] = min(ans[v], d[lvl[v]][u]);
}
ll query(int u) {
ll ret = 1e18;
for(int v = u; v + 1; v = p[v])
ret = min(ret, ans[v] + d[lvl[v]][u]);
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
int u = A[i], v = B[i], c = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
cost[u].push_back(c);
cost[v].push_back(c);
}
for(int i = 0; i < N; i++)
ans[i] = 1e18;
decompose(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
if(S < T) {
for(int i = 0; i < S; i++)
update(X[i]);
ll ret = 1e18;
for(int i = 0; i < T; i++)
ret = min(ret, query(Y[i]));
for(int i = 0; i < S; i++) {
for(int v = X[i]; v + 1; v = p[v])
ans[v] = 1e18;
} return ret;
} else {
for(int i = 0; i < T; i++)
update(Y[i]);
ll ret = 1e18;
for(int i = 0; i < S; i++)
ret = min(ret, query(X[i]));
for(int i = 0; i < T; i++) {
for(int v = Y[i]; v + 1; v = p[v])
ans[v] = 1e18;
} return ret;
}
}
Compilation message
factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
24440 KB |
Output is correct |
2 |
Correct |
370 ms |
42672 KB |
Output is correct |
3 |
Correct |
413 ms |
52188 KB |
Output is correct |
4 |
Correct |
392 ms |
61664 KB |
Output is correct |
5 |
Correct |
448 ms |
71360 KB |
Output is correct |
6 |
Correct |
392 ms |
80208 KB |
Output is correct |
7 |
Correct |
500 ms |
90212 KB |
Output is correct |
8 |
Correct |
497 ms |
94936 KB |
Output is correct |
9 |
Correct |
523 ms |
95244 KB |
Output is correct |
10 |
Correct |
289 ms |
95244 KB |
Output is correct |
11 |
Correct |
463 ms |
95244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
95244 KB |
Output is correct |
2 |
Correct |
3619 ms |
197868 KB |
Output is correct |
3 |
Correct |
4742 ms |
213924 KB |
Output is correct |
4 |
Correct |
1126 ms |
213924 KB |
Output is correct |
5 |
Correct |
7145 ms |
237760 KB |
Output is correct |
6 |
Correct |
4613 ms |
237760 KB |
Output is correct |
7 |
Correct |
1349 ms |
237760 KB |
Output is correct |
8 |
Correct |
498 ms |
237760 KB |
Output is correct |
9 |
Correct |
1968 ms |
237760 KB |
Output is correct |
10 |
Correct |
1363 ms |
237760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
24440 KB |
Output is correct |
2 |
Correct |
370 ms |
42672 KB |
Output is correct |
3 |
Correct |
413 ms |
52188 KB |
Output is correct |
4 |
Correct |
392 ms |
61664 KB |
Output is correct |
5 |
Correct |
448 ms |
71360 KB |
Output is correct |
6 |
Correct |
392 ms |
80208 KB |
Output is correct |
7 |
Correct |
500 ms |
90212 KB |
Output is correct |
8 |
Correct |
497 ms |
94936 KB |
Output is correct |
9 |
Correct |
523 ms |
95244 KB |
Output is correct |
10 |
Correct |
289 ms |
95244 KB |
Output is correct |
11 |
Correct |
463 ms |
95244 KB |
Output is correct |
12 |
Correct |
27 ms |
95244 KB |
Output is correct |
13 |
Correct |
3619 ms |
197868 KB |
Output is correct |
14 |
Correct |
4742 ms |
213924 KB |
Output is correct |
15 |
Correct |
1126 ms |
213924 KB |
Output is correct |
16 |
Correct |
7145 ms |
237760 KB |
Output is correct |
17 |
Correct |
4613 ms |
237760 KB |
Output is correct |
18 |
Correct |
1349 ms |
237760 KB |
Output is correct |
19 |
Correct |
498 ms |
237760 KB |
Output is correct |
20 |
Correct |
1968 ms |
237760 KB |
Output is correct |
21 |
Correct |
1363 ms |
237760 KB |
Output is correct |
22 |
Correct |
3782 ms |
237760 KB |
Output is correct |
23 |
Correct |
4146 ms |
237760 KB |
Output is correct |
24 |
Correct |
5840 ms |
237760 KB |
Output is correct |
25 |
Correct |
6098 ms |
237760 KB |
Output is correct |
26 |
Correct |
6463 ms |
237760 KB |
Output is correct |
27 |
Correct |
7537 ms |
237760 KB |
Output is correct |
28 |
Correct |
1786 ms |
237760 KB |
Output is correct |
29 |
Correct |
6587 ms |
238672 KB |
Output is correct |
30 |
Correct |
5614 ms |
238672 KB |
Output is correct |
31 |
Correct |
6402 ms |
247096 KB |
Output is correct |
32 |
Correct |
1755 ms |
247096 KB |
Output is correct |
33 |
Correct |
569 ms |
247096 KB |
Output is correct |
34 |
Correct |
1140 ms |
247096 KB |
Output is correct |
35 |
Correct |
1292 ms |
247096 KB |
Output is correct |
36 |
Correct |
1871 ms |
247096 KB |
Output is correct |
37 |
Correct |
1884 ms |
247096 KB |
Output is correct |