#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define fs first
#define sc second
#define rng(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) rng(i,0,n)
#define vec vector
#define siz(a) (a.size())
#define pb push_back
template<typename T>
void chmax(T &a,T b){a=max(a,b);}
template<typename T>
void chmin(T &a,T b){a=min(a,b);}
constexpr ll inf=1e17;
int n;
ll dpt[600000],dpt2[600000];
int pa[600000];
vec<bool>dead;
int root;
vec<int>tree[600000];
int par[600000];
vec<H>e[600000];
vec<int>eul,out;
int spt[1300000][20];
int lgt[1300000];
int id[1300000];
ll lca2(int x,int y){
ll ret=0;
x=id[x],y=id[y];
if(x>y) swap(x,y);
int k=lgt[y-x];
x=spt[x][k];
y=spt[y-(1<<k)+1][k];
if(eul[spt[x][0]]<eul[spt[y][0]]) return out[spt[x][0]];
else return out[spt[y][0]];
}
ll lca(int x,int y){
int k=lca2(x,y);
return dpt[x]+dpt[y]-2*dpt[k];
}
int octr(int x){
static int sz[600000];
auto rec=[&](int pos,int p, auto& rec)->void{
sz[pos]=1;
for(auto g:e[pos]){
if(g.fs==p||dead[g.fs]) continue;
rec(g.fs,pos,rec);
sz[pos]+=sz[g.fs];
}
};
rec(x,-1,rec);
int N=sz[x];
auto dfs=[&](int pos,int p,auto& dfs)->int{
for(auto g:e[pos]){
if(g.fs==p||dead[g.fs]) continue;
if(sz[g.fs]>N/2) return dfs(g.fs,pos,dfs);
}
return pos;
};
return dfs(x,-1,dfs);
}
int build(int x){
int c=octr(x);
dead[c]=1;
if(root==-1) root=c;
for(auto g:e[c]){
if(dead[g.fs])continue;
int k=build(g.fs);
tree[c].pb(k);
par[k]=c;
}
return c;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
rep(i,n-1){
e[A[i]].pb(H{B[i],D[i]});
e[B[i]].pb(H{A[i],D[i]});
}
auto dfs=[&](int x,int p,ll d,int d2,auto& dfs)->void{
dpt[x]=d,pa[x]=p,dpt2[x]=d2;
for(auto g:e[x]){
if(g.fs==p) continue;
eul.pb(dpt2[x]);out.pb(x);
dfs(g.fs, x, d+g.sc,d2+1, dfs);
}
id[x]=siz(eul);
eul.pb(dpt2[x]);out.pb(x);
};
dfs(0,-1,0,0,dfs);
rep(i,siz(eul)) spt[i][0]=i;
rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;
rep(i,19)for(int j=0;j+(1<<i)<=siz(eul);j++){
int idx1=spt[j][i],idx2=spt[j+(1<<i)][i];
if(eul[idx1]<eul[idx2]) spt[j][i+1]=idx1;
else spt[j][i+1]=idx2;
}
root=-1;
dead.assign(n,false);
build(0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans=inf;
unordered_map<int, ll>mp;
rep(i,S){
int t=X[i]; mp[t]=0;
do{
t=par[t];
if(mp.find(t)==mp.end()) mp[t]=lca(t,X[i]);
else chmin(mp[t],lca(t,X[i]));
}while(t!=root);
}
rep(i,T){
int t=Y[i];
if(mp.find(t)!=mp.end()) chmin(ans,mp[t]);
do{
t=par[t];
if(mp.find(t)!=mp.end()) chmin(ans,lca(Y[i],t)+mp[t]);
}while(t!=root);
}
return ans;
}
Compilation message
factories.cpp: In function 'll lca2(int, int)':
factories.cpp:37:6: warning: unused variable 'ret' [-Wunused-variable]
37 | ll ret=0;
| ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
| ^
factories.cpp:13:18: note: in expansion of macro 'rng'
13 | #define rep(i,n) rng(i,0,n)
| ^~~
factories.cpp:103:3: note: in expansion of macro 'rep'
103 | rep(i,siz(eul)) spt[i][0]=i;
| ^~~
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
| ^
factories.cpp:104:3: note: in expansion of macro 'rng'
104 | rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;
| ^~~
factories.cpp:106:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | rep(i,19)for(int j=0;j+(1<<i)<=siz(eul);j++){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
29164 KB |
Output is correct |
| 2 |
Correct |
1114 ms |
39272 KB |
Output is correct |
| 3 |
Correct |
1650 ms |
39324 KB |
Output is correct |
| 4 |
Correct |
1217 ms |
39492 KB |
Output is correct |
| 5 |
Correct |
1564 ms |
39808 KB |
Output is correct |
| 6 |
Correct |
510 ms |
39148 KB |
Output is correct |
| 7 |
Correct |
1589 ms |
39364 KB |
Output is correct |
| 8 |
Correct |
1625 ms |
39276 KB |
Output is correct |
| 9 |
Correct |
1601 ms |
40044 KB |
Output is correct |
| 10 |
Correct |
498 ms |
39020 KB |
Output is correct |
| 11 |
Correct |
1596 ms |
39244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28908 KB |
Output is correct |
| 2 |
Correct |
4807 ms |
180168 KB |
Output is correct |
| 3 |
Correct |
6974 ms |
186064 KB |
Output is correct |
| 4 |
Correct |
1836 ms |
176812 KB |
Output is correct |
| 5 |
Execution timed out |
8053 ms |
232892 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
29164 KB |
Output is correct |
| 2 |
Correct |
1114 ms |
39272 KB |
Output is correct |
| 3 |
Correct |
1650 ms |
39324 KB |
Output is correct |
| 4 |
Correct |
1217 ms |
39492 KB |
Output is correct |
| 5 |
Correct |
1564 ms |
39808 KB |
Output is correct |
| 6 |
Correct |
510 ms |
39148 KB |
Output is correct |
| 7 |
Correct |
1589 ms |
39364 KB |
Output is correct |
| 8 |
Correct |
1625 ms |
39276 KB |
Output is correct |
| 9 |
Correct |
1601 ms |
40044 KB |
Output is correct |
| 10 |
Correct |
498 ms |
39020 KB |
Output is correct |
| 11 |
Correct |
1596 ms |
39244 KB |
Output is correct |
| 12 |
Correct |
24 ms |
28908 KB |
Output is correct |
| 13 |
Correct |
4807 ms |
180168 KB |
Output is correct |
| 14 |
Correct |
6974 ms |
186064 KB |
Output is correct |
| 15 |
Correct |
1836 ms |
176812 KB |
Output is correct |
| 16 |
Execution timed out |
8053 ms |
232892 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
