#include <bits/stdc++.h>
#include "factories.h"
#pragma message("Compiling at: " __TIMESTAMP__ ". Executing File: " __FILE__ ". If this date is not the same as the submission date, it could be an indication that the submission was rejudged.")
#ifdef DEBUG
#pragma message("Attention, this program is running in DEBUG mode! Performance will be affected")
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#endif
using namespace std;
#define ll long long
#define lp pair<ll,ll>
#define ld long double
#define ms(x, y) memset(x, 0, sizeof(x))
#define l2(x) ((x==0)? 0 :31 - __builtin_clz(x))
int cur = 0;
int head[500001], vnext[1000001], adj[1000001], weight[1000001];
int cnt[500001];
int cqstat[500001];
bitset<500001> blocked;
int parent[500001];
ll ct_val[500001];
ll ct_dist[20][500001];
int depth[500001];
//int find_centroid(int x, int p, int sz){
// for(int i = head[x]; i != -1; i = vnext[i]){
// if(adj[i] != p && !blocked[adj[i]] && cnt[adj[i]] > sz / 2){
// return find_centroid(adj[i], x, sz);
// }
// }
// return x;
//}
int ffind_centroid(int x){
//visited.reset();
int sz = cnt[x];
int v = x;
int p = -1;
while(true){
bool any = false;
for(int i = head[v]; i != -1; i = vnext[i]){
if(adj[i] != p && !blocked[adj[i]] && cnt[adj[i]] * 2 > sz){
p = v;
v = adj[i];
any = true;
break;
}
}
if(!any) return v;
}
}
int tlen = 0;
int req_tour[500001];
int req_size(int x, int p){
if(blocked[x]) return 0;
cnt[x] = 1;
// req_tour[tlen++] = x;
for(int i = head[x]; i != -1; i = vnext[i]){
if(adj[i] != p && !blocked[x]){
cnt[x] += req_size(adj[i], x);
}
}
return cnt[x];
}
void req_dist(int x, int p, int d){
if(blocked[x]) return;
for(int i = head[x]; i != -1; i = vnext[i]){
if(adj[i] != p && !blocked[x]){
ct_dist[d][adj[i]] = ct_dist[d][x] + weight[i];
req_dist(adj[i], x, d);
}
}
}
void build_centroid_tree(int x, int p, int d){
tlen = 0;
req_size(x, x);
x = ffind_centroid(x);
depth[x] = d;
req_dist(x, x, d);
blocked[x] = true;
parent[x] = p;
for(int i = head[x]; i != -1; i = vnext[i]){
if(!blocked[adj[i]]){
build_centroid_tree(adj[i], x, d+1);
}
}
}
#define get_dist(c,i) (ct_dist[depth[c]][i])
void update(int x, int qstat){
int idx = 0;
for(int c = x; c != -1; c = parent[c]){
ll d = get_dist(c,x);
if(cqstat[c] != qstat) {
ct_val[c] = d;
cqstat[c] = qstat;
}
ct_val[c] = min(ct_val[c], d);
idx++;
}
}
ll query(int x, int qstat){
int q = 0;
ll minv = 1e17;
for(int c = x ; c != -1; c = parent[c]) {
ll d = get_dist(c,x);
if(cqstat[c] == qstat){
minv = min(minv, ct_val[c] + d);
}
q++;
}
return minv;
}
void update2(int x){
for(int c = x; c != -1; c = parent[c]){
ll d = get_dist(c,x);
ct_val[c] = min(ct_val[c], d);
}
}
void clean(int x){
for(int c = x; c != -1; c = parent[c]){
ct_val[c] = 1e17;
}
}
ll query2(int x){
ll minv = 1e17;
for(int c = x ; c != -1; c = parent[c]) {
ll d = get_dist(c,x);
minv = min(minv, ct_val[c] + d);
}
return minv;
}
void Init(int N, int A[], int B[], int D[]){
fill(ct_val, ct_val + 500001, 1e17);
fill(parent, parent + 500001, -1);
fill(head, head + 500001, -1);
int x = 0;
for(int i =0 ; i < N-1; i++){
int u = A[i];
int v = B[i];
adj[cur] = v; weight[cur] = D[i]; vnext[cur] = head[u]; head[u] = cur++;
adj[cur] = u; weight[cur] = D[i]; vnext[cur] = head[v]; head[v] = cur++;
x = A[i];
}
auto start = chrono::system_clock::now();
build_centroid_tree(x, -1, 0);
auto dur = chrono::duration<double, std::milli>(chrono::system_clock::now() - start).count();
assert(dur <= 1000);
}
int curqstat = 1;
ll Query(int S, int X[], int T, int Y[]){
if(false){
curqstat++;
for(int i = 0; i < S; i++){
update(X[i], curqstat);
}
ll mind = 1e17;
for(int i = 0; i < T; i++){
mind = min(mind, query(Y[i], curqstat));
}
return mind;
}
for(int i = 0; i < S; i++){
update2(X[i]);
}
ll mind = 1e17;
for(int i = 0; i < T; i++){
mind = min(mind, query2(Y[i]));
}
for(int i = 0; i < S; i++){
clean(X[i]);
}
return mind;
}
//int main(){
// int N, Q;
// assert(scanf("%i %i", &N, &Q) == 2);
// int *A = (int*)malloc(sizeof(int) * (N - 1));
// int *B = (int*)malloc(sizeof(int) * (N - 1));
// int *D = (int*)malloc(sizeof(int) * (N - 1));
// for(int a = 0; a < N - 1; a++){
// assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
// }
// Init(N, A, B, D);
// for(int a = 0; a < Q; a++){
// int S, T;
// assert(scanf("%i %i", &S, &T) == 2);
// int *X = (int*)malloc(sizeof(int) * S);
// int *Y = (int*)malloc(sizeof(int) * T);
// for(int b = 0; b < S; b++){
// assert(scanf("%i", X + b) == 1);
// }
// for(int b = 0; b < T; b++){
// assert(scanf("%i", Y + b) == 1);
// }
// printf("%i\n", Query(S, X, T, Y));
// free(X);
// free(Y);
// }
// free(A);
// free(B);
// free(D);
//}
Compilation message
factories.cpp:3:194: note: #pragma message: Compiling at: Mon May 3 23:25:07 2021. Executing File: factories.cpp. If this date is not the same as the submission date, it could be an indication that the submission was rejudged.
3 | #pragma message("Compiling at: " __TIMESTAMP__ ". Executing File: " __FILE__ ". If this date is not the same as the submission date, it could be an indication that the submission was rejudged.")
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8652 KB |
Output is correct |
| 2 |
Correct |
365 ms |
17008 KB |
Output is correct |
| 3 |
Correct |
392 ms |
16996 KB |
Output is correct |
| 4 |
Correct |
388 ms |
17056 KB |
Output is correct |
| 5 |
Correct |
421 ms |
17316 KB |
Output is correct |
| 6 |
Correct |
271 ms |
16452 KB |
Output is correct |
| 7 |
Correct |
397 ms |
17116 KB |
Output is correct |
| 8 |
Correct |
389 ms |
17012 KB |
Output is correct |
| 9 |
Correct |
419 ms |
17264 KB |
Output is correct |
| 10 |
Correct |
267 ms |
16460 KB |
Output is correct |
| 11 |
Correct |
388 ms |
17056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8396 KB |
Output is correct |
| 2 |
Runtime error |
1551 ms |
190208 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8652 KB |
Output is correct |
| 2 |
Correct |
365 ms |
17008 KB |
Output is correct |
| 3 |
Correct |
392 ms |
16996 KB |
Output is correct |
| 4 |
Correct |
388 ms |
17056 KB |
Output is correct |
| 5 |
Correct |
421 ms |
17316 KB |
Output is correct |
| 6 |
Correct |
271 ms |
16452 KB |
Output is correct |
| 7 |
Correct |
397 ms |
17116 KB |
Output is correct |
| 8 |
Correct |
389 ms |
17012 KB |
Output is correct |
| 9 |
Correct |
419 ms |
17264 KB |
Output is correct |
| 10 |
Correct |
267 ms |
16460 KB |
Output is correct |
| 11 |
Correct |
388 ms |
17056 KB |
Output is correct |
| 12 |
Correct |
5 ms |
8396 KB |
Output is correct |
| 13 |
Runtime error |
1551 ms |
190208 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
