#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 fl2[3000001];
int cur = 0;
int head[500001], vnext[1000001], adj[1000001], weight[1000001];
int ett_idx = 1;
int ettd[20][2000001];
int ettd2[20][2000001];
int in[500001];
int cnt[500001];
int cqstat[500001];
bitset<500001> blocked;
int parent[500001];
ll ct_val[500001];
ll dist[500001];
int depth[500001];
ll cdist[20][500001];
int cparent[500001];
inline int func(int a, int a1, int b, int b1){
if(a < b) return a1;
return b1;
}
inline int lca_rmq(int l, int r){
int sz = fl2[r - l + 1];
return func(ettd[sz][l], ettd2[sz][l], ettd[sz][r - (1 << sz) + 1], ettd2[sz][r - (1 << sz) + 1]);
}
int req_size(int x, int p){
if(blocked[x]) return 0;
cnt[x] = 1;
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 ett(int x, int p){
in[x] = ett_idx;
ettd[0][ett_idx] = depth[x];
ettd2[0][ett_idx++] = x;
for(int i = head[x]; i != -1; i = vnext[i]){
int v = adj[i];
int w = weight[i];
if(v != p){
depth[v] = depth[x] + 1;
dist[v] = dist[x] + w;
ett(v, x);
ettd[0][ett_idx] = depth[x];
ettd2[0][ett_idx++] = x;
}
}
}
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]] > sz / 2){
p = v;
v = adj[i];
any = true;
break;
}
}
if(!any) return v;
}
}
void build_centroid_tree(int x, int p, int d = 0){
req_size(x, p);
//x = find_centroid(x, -1, cnt[x]);
x = ffind_centroid(x);
parent[x] = p;
blocked[x] = true;
for(int i = head[x]; i != -1; i = vnext[i]){
if(!blocked[adj[i]]){
build_centroid_tree(adj[i], x, d + 1);
}
}
}
inline ll lca_d(int a, int b){
int x = in[a];
int y = in[b];
if(x > y) swap(x,y);
int anc = lca_rmq(x,y);
return dist[a] + dist[b] - 2 * dist[anc];
}
void update(int x, int qstat){
int idx = 0;
for(int c = x; c != -1; c = parent[c]){
if(cdist[idx][x] == -1) cdist[idx][x] = lca_d(c, x);
if(cqstat[c] != qstat) {
ct_val[c] = cdist[idx][x];
cqstat[c] = qstat;
}
ct_val[c] = min(ct_val[c], cdist[idx][x]);
idx++;
}
}
ll query(int x, int qstat){
int q = 0;
ll minv = 1e17;
for(int c = x ; c != -1; c = parent[c]) {
if(cdist[q][x] == -1) cdist[q][x] = lca_d(c, x);
if(cqstat[c] == qstat){
minv = min(minv, ct_val[c] + cdist[q][x]);
}
q++;
}
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);
for(int i = 0; i < 20; i++){
fill(cdist[i], cdist[i] + 500001, -1);
}
for(int i = 1; i <= 3000000; i++){
fl2[i] = l2(i);
}
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];
}
build_centroid_tree(x, -1);
ett(x,x);
for(int i = 1; i < fl2[ett_idx+1] + 1; i++){
for(int j = 0; j + (1 << i) <= ett_idx+1; j++){
if(ettd[i-1][j] < ettd[i-1][j + (1 << (i-1))]){
ettd[i][j] = ettd[i-1][j];
ettd2[i][j] = ettd2[i-1][j];
}else{
ettd[i][j] = ettd[i-1][j + (1 << (i-1))];
ettd2[i][j] = ettd2[i-1][j + (1 << (i-1))];
}
}
}
auto start = chrono::system_clock::now();
// for(int i = 0; i < N; i++){
// int idx = 0;
// for(int c = i; c != -1; c = parent[c]){
// cdist[idx][i] = lca_d(c, i);
// idx++;
// }
// cparent[i] = idx;
// }
auto dur = chrono::duration<double, std::milli>(chrono::system_clock::now() - start).count();
assert(dur <= 500);
}
int curqstat = 1;
ll Query(int S, int X[], int T, int Y[]){
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;
}
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:57 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.")
| ^
factories.cpp: In function 'int main()':
factories.cpp:218:18: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
218 | printf("%i\n", Query(S, X, T, Y));
| ~^ ~~~~~~~~~~~~~~~~~
| | |
| int long long int
| %lli
/tmp/ccJuIhMZ.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccxqjoT2.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
