#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll int
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 19;
vector<pair<ll, ll>> node[N];
ll dep[N], tin[N];
long long dis[N];
ll sz[N];
ll par[N];
long long ans[N];
bool ok[N], in[N];
vector<ll> idx[N];
ll timer = 0;
pair<ll, ll> dp[20][N * 2];
void dfs(ll u, ll p){
timer++;
idx[u].push_back(timer);
tin[timer] = u;
for (auto j : node[u]){
if (j.first == p) continue;
dis[j.first] = dis[u] + j.second;
dep[j.first] = dep[u] + 1;
dfs(j.first, u);
timer++;
tin[timer] = u;
idx[u].push_back(timer);
}
}
void buildLCA(){
for (int i = 1; i <= timer; i++) dp[0][i] = {dep[tin[i]], tin[i]};
for (int i = 1; i <= lg; i++){
for (int j = 1; j <= timer; j++){
if ((j + (1 << i)) > timer) break;
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
}
}
}
ll findnewCT(ll u, ll p, ll S){
for (auto j : node[u]){
if (j.first == p || in[j.first]) continue;
if ((sz[j.first] * 2) > S) return findnewCT(j.first, u, S);
}
return u;
}
void initsz(ll u, ll p){
sz[u] = 1;
for (auto j : node[u]){
if (j.first == p || in[j.first]) continue;
initsz(j.first, u);
sz[u] += sz[j.first];
}
}
ll findCT(ll u, ll S){
initsz(u, u);
u = findnewCT(u, u, S);
in[u] = 1;
for (auto j : node[u]){
if (in[j.first]) continue;
if (sz[j.first] > sz[u]){
ll x = findCT(j.first, S - sz[u]);
par[x] = u;
} else {
ll x = findCT(j.first, sz[j.first]);
par[x] = u;
}
}
return u;
}
ll LCA(ll u, ll v){
ll l = idx[u][0], r = idx[v][0];
if (l > r) swap(l, r);
ll k = 31 - __builtin_clz(r - l + 1);
return min(dp[k][l], dp[k][r - (1 << k) + 1]).second;
}
long long dist(ll u, ll v){
ll lca = LCA(u, v);
return dis[u] + dis[v] - 2 * dis[lca];
}
vector<ll> recover;
void upd(ll u, ll root){
if (!ok[u]) recover.push_back(u), ok[u] = 1;
if (u == 0) return;
ans[u] = min(ans[u], dist(root, u));
upd(par[u], root);
}
long long get(ll u, ll root){
if (u == 0) return 1e18;
return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
recover.clear();
for (int i = 1; i <= T; i++){
upd(Y[i - 1] + 1, Y[i - 1] + 1);
}
long long res = 1e18;
for (int i = 1; i <= S; i++){
res = min(res, get(X[i - 1] + 1, X[i - 1] + 1));
}
for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
/*
for (int i = 1; i <= T; i++){
ll now = Y[i - 1] + 1;
while (now){
ans[now] = 1e15;
now = par[now];
}
}
*/
return res;
}
void Init(int n, int A[], int B[], int D[]){
for (int i = 1; i < n; i++){
node[A[i - 1] + 1].push_back({B[i - 1] + 1, D[i - 1]});
node[B[i - 1] + 1].push_back({A[i - 1] + 1, D[i - 1]});
}
dfs(1, 1);
buildLCA();
ll root = findCT(1, n);
for (int i = 1; i <= n; i++) ans[i] = 1e15;
}
/*
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("VietCT.INP", "r")){
freopen("VietCT.INP", "r", stdin);
freopen("VietCT.OUT", "w", stdout);
}
}
*/
/*
*/
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:125:12: warning: unused variable 'root' [-Wunused-variable]
125 | ll root = findCT(1, n);
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
47864 KB |
Output is correct |
2 |
Correct |
680 ms |
57208 KB |
Output is correct |
3 |
Correct |
877 ms |
57080 KB |
Output is correct |
4 |
Correct |
863 ms |
57084 KB |
Output is correct |
5 |
Correct |
952 ms |
57568 KB |
Output is correct |
6 |
Correct |
385 ms |
57080 KB |
Output is correct |
7 |
Correct |
879 ms |
57208 KB |
Output is correct |
8 |
Correct |
890 ms |
57108 KB |
Output is correct |
9 |
Correct |
936 ms |
57336 KB |
Output is correct |
10 |
Correct |
381 ms |
57336 KB |
Output is correct |
11 |
Correct |
880 ms |
57268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
47616 KB |
Output is correct |
2 |
Correct |
3805 ms |
262360 KB |
Output is correct |
3 |
Correct |
4907 ms |
265424 KB |
Output is correct |
4 |
Correct |
1439 ms |
265656 KB |
Output is correct |
5 |
Correct |
6649 ms |
293432 KB |
Output is correct |
6 |
Correct |
5344 ms |
267288 KB |
Output is correct |
7 |
Correct |
3816 ms |
97000 KB |
Output is correct |
8 |
Correct |
1136 ms |
97948 KB |
Output is correct |
9 |
Correct |
4469 ms |
101032 KB |
Output is correct |
10 |
Correct |
3864 ms |
98380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
47864 KB |
Output is correct |
2 |
Correct |
680 ms |
57208 KB |
Output is correct |
3 |
Correct |
877 ms |
57080 KB |
Output is correct |
4 |
Correct |
863 ms |
57084 KB |
Output is correct |
5 |
Correct |
952 ms |
57568 KB |
Output is correct |
6 |
Correct |
385 ms |
57080 KB |
Output is correct |
7 |
Correct |
879 ms |
57208 KB |
Output is correct |
8 |
Correct |
890 ms |
57108 KB |
Output is correct |
9 |
Correct |
936 ms |
57336 KB |
Output is correct |
10 |
Correct |
381 ms |
57336 KB |
Output is correct |
11 |
Correct |
880 ms |
57268 KB |
Output is correct |
12 |
Correct |
34 ms |
47616 KB |
Output is correct |
13 |
Correct |
3805 ms |
262360 KB |
Output is correct |
14 |
Correct |
4907 ms |
265424 KB |
Output is correct |
15 |
Correct |
1439 ms |
265656 KB |
Output is correct |
16 |
Correct |
6649 ms |
293432 KB |
Output is correct |
17 |
Correct |
5344 ms |
267288 KB |
Output is correct |
18 |
Correct |
3816 ms |
97000 KB |
Output is correct |
19 |
Correct |
1136 ms |
97948 KB |
Output is correct |
20 |
Correct |
4469 ms |
101032 KB |
Output is correct |
21 |
Correct |
3864 ms |
98380 KB |
Output is correct |
22 |
Correct |
5386 ms |
266128 KB |
Output is correct |
23 |
Correct |
5459 ms |
267636 KB |
Output is correct |
24 |
Correct |
7515 ms |
267780 KB |
Output is correct |
25 |
Correct |
7338 ms |
271528 KB |
Output is correct |
26 |
Correct |
7728 ms |
267892 KB |
Output is correct |
27 |
Execution timed out |
8102 ms |
289688 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |