#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
// Anything related to centroid is here
int levelC[500005];
int subtreeSizeC[500005];
long long distC[500005][22];
int pC[500005];
// Anything related to original tree is here
vector<ii> AdjList[500005];
int p[500005][22];
int depth[500005];
long long dist[500005];
int dfs1(int u, int p, int level){
subtreeSizeC[u] = 1;
for(ii temp: AdjList[u]){
int v = temp.first;
if(levelC[v] != -1 || v == p){continue;}
subtreeSizeC[u] += dfs1(v, u, level);
}
return subtreeSizeC[u];
}
int dfs2(int u, int p, int subtreeSize){
for(ii temp: AdjList[u]){
int v = temp.first;
if(levelC[v] != -1){continue;}
if(v != p && subtreeSizeC[v] > subtreeSize/2){
// move there
return dfs2(v, u, subtreeSize);
}
}
return u; // this is the centroid
}
void build(int u, int p, int level){
//printf("build(%d, %d, %d)\n", u, p, level);
int subtreeSize = dfs1(u, p, level);
int centroid = dfs2(u, p, subtreeSize);
//if(p == -1){p = centroid;}
pC[centroid] = p; // maybe we should allow -1
//printf("build(%d, %d, %d): levelC[%d]=%d subtreeSize=%d\n", u, p, level, centroid, level, subtreeSize);
levelC[centroid] = level;
for(ii temp: AdjList[centroid]){
int v = temp.first;
if(levelC[v] != -1){continue;} // already assigned
build(v, centroid, level+1);
}
}
int lca(int a, int b){
if(depth[a] < depth[b]){
swap(a, b);
}
for(int k = 21; k >= 0; k --){
if(p[a][k] == -1){continue;}
if(depth[p[a][k]] >= depth[b]){
a = p[a][k];
}
}
if(a == b){return a;}
for(int k = 21; k >= 0; k --){
if(p[a][k] != p[b][k]){
a = p[a][k];
b = p[b][k];
}
}
return p[a][0];
}
long long distO(int a, int b){
int lca1 = lca(a, b);
return dist[a] + dist[b] - 2*dist[lca1];
}
void init2(int N){
memset(levelC, -1, sizeof(levelC));
memset(subtreeSizeC, -1, sizeof(subtreeSizeC));
memset(distC, -1, sizeof(distC));
memset(pC, -1, sizeof(pC));
build(0, -1, 0); // build(1, -1, 0) for 1-index
/*for(int i = 0; i <= N; i ++){
printf("levelC[%d]=%d\n", i, levelC[i]);
}*/
int op = 0;
/*for(int u = 0; u <= N; u ++){
int v = u;
for(int k = levelC[u]; k >= 0; k --){
op ++;
distC[u][k] = distO(u, v);
assert(op < 6e6);
//printf("%d %d level=%d dist=%lld\n", u, v, k, distC[u][k]);
v = pC[v];
}
}*/
//assert(N <= 5000);
}
const long long INF = (3LL << 60);
vector<int> to_update;
bool updated[500005];
long long ans[500005][2];
long long op = 0;
void update(int u, int set1){
int v = u;
for(int k = levelC[u]; k >= 0; k --){
if(distC[u][k] == -1){
distC[u][k] = distO(u, v);
}
ans[v][set1] = min(ans[v][set1], distC[u][k]);
if(!updated[v]){
updated[v] = true;
op ++;
to_update.push_back(v);
}
v = pC[v];
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; i ++){
AdjList[A[i]].push_back(ii(B[i], D[i]));
AdjList[B[i]].push_back(ii(A[i], D[i]));
}
// Rooting tree using BFS to avoid confusion in centroid decomposition...
memset(p, -1, sizeof(p));
memset(depth, -1, sizeof(depth));
memset(dist, -1, sizeof(dist));
queue<int> q;
q.push(0);
depth[0] = 0;
dist[0] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(ii v: AdjList[u]){
if(depth[v.first] == -1){
depth[v.first] = depth[u] + 1;
dist[v.first] = dist[u] + v.second;
p[v.first][0] = u;
q.push(v.first);
}
}
}
for(int k = 1; k <= 21; k ++){
for(int i = 0; i <= N; i ++){
if(p[i][k-1] == -1){
p[i][k] = -1;
}else{
p[i][k] = p[p[i][k-1]][k-1];
}
}
}
init2(N);
for(int i = 0; i <= N; i ++){
ans[i][0] = INF;
ans[i][1] = INF;
}
memset(updated, false, sizeof(updated));
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i ++){
update(X[i], 0);
}
for(int i = 0; i < T; i ++){
update(Y[i], 1);
}
long long result = INF;
for(int i: to_update){
result = min(result, ans[i][0] + ans[i][1]);
}
for(int i: to_update){
ans[i][0] = INF;
ans[i][1] = INF;
updated[i] = false;
}
to_update.clear();
return result;
}
Compilation message
factories.cpp: In function 'void init2(int)':
factories.cpp:94:9: warning: unused variable 'op' [-Wunused-variable]
int op = 0;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
153976 KB |
Output is correct |
| 2 |
Correct |
544 ms |
166060 KB |
Output is correct |
| 3 |
Correct |
615 ms |
166004 KB |
Output is correct |
| 4 |
Correct |
590 ms |
165848 KB |
Output is correct |
| 5 |
Correct |
645 ms |
166112 KB |
Output is correct |
| 6 |
Correct |
468 ms |
165972 KB |
Output is correct |
| 7 |
Correct |
615 ms |
167544 KB |
Output is correct |
| 8 |
Correct |
616 ms |
168540 KB |
Output is correct |
| 9 |
Correct |
625 ms |
171712 KB |
Output is correct |
| 10 |
Correct |
455 ms |
171388 KB |
Output is correct |
| 11 |
Correct |
616 ms |
171480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
153636 KB |
Output is correct |
| 2 |
Correct |
3205 ms |
201840 KB |
Output is correct |
| 3 |
Execution timed out |
8058 ms |
204180 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
153976 KB |
Output is correct |
| 2 |
Correct |
544 ms |
166060 KB |
Output is correct |
| 3 |
Correct |
615 ms |
166004 KB |
Output is correct |
| 4 |
Correct |
590 ms |
165848 KB |
Output is correct |
| 5 |
Correct |
645 ms |
166112 KB |
Output is correct |
| 6 |
Correct |
468 ms |
165972 KB |
Output is correct |
| 7 |
Correct |
615 ms |
167544 KB |
Output is correct |
| 8 |
Correct |
616 ms |
168540 KB |
Output is correct |
| 9 |
Correct |
625 ms |
171712 KB |
Output is correct |
| 10 |
Correct |
455 ms |
171388 KB |
Output is correct |
| 11 |
Correct |
616 ms |
171480 KB |
Output is correct |
| 12 |
Correct |
135 ms |
153636 KB |
Output is correct |
| 13 |
Correct |
3205 ms |
201840 KB |
Output is correct |
| 14 |
Execution timed out |
8058 ms |
204180 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
