#include "factories.h"
#include<bits/stdc++.h>
#define MAX_N 500000
#define MAX_Q 100000
#define MAX_SUM_ST 1000000
#define MAX_VALUE 1000000000
using namespace std;
const int nmax=5e5+42;
const long long inf=1e18;
static int N, Q;
static int A[MAX_N], B[MAX_N], D[MAX_N];
static int S[MAX_N];
static int T[MAX_N];
static int X[MAX_SUM_ST];
static int Y[MAX_SUM_ST];
static int Qx[MAX_N];
static int Qy[MAX_N];
int n;
vector< pair<int/*to*/,int/*cost*/> > adj[nmax];
int height[nmax];
long long depth[nmax];
int t,in[nmax],out[nmax];
pair<int/*height*/,int/*node*/> table[22][nmax];
void dfs(int node,int par,int h,long long sum)
{
height[node]=h;
depth[node]=sum;
t++;
in[node]=t;
table[0][t]={height[node],node};
for(auto k:adj[node])
if(k.first!=par)
{
dfs(k.first,node,h+1,sum+k.second);
t++;
table[0][t]={height[node],node};
}
out[node]=t;
}
bool been[nmax];
int SZ[nmax];
void dfs_sz(int node,int par)
{
SZ[node]=1;
for(auto k:adj[node])
if(k.first!=par&&been[k.first]==0)
{
dfs_sz(k.first,node);
SZ[node]+=SZ[k.first];
}
}
int centroid(int node)
{
dfs_sz(node,node);
int req=(SZ[node]+1)/2;
while(SZ[node]>req)
{
bool stop=1;
for(auto k:adj[node])
if(SZ[node]>SZ[k.first]&&SZ[k.first]>req)
{
node=k.first;
stop=0;
}
if(stop)break;
}
return node;
}
vector<int> centroid_paths[nmax];
void note_paths(int node,int par,int centroid)
{
centroid_paths[node].push_back(centroid);
for(auto k:adj[node])
if(k.first!=par&&been[k.first]==0)
note_paths(k.first,node,centroid);
}
void create_centroid(int node)
{
node=centroid(node);
note_paths(node,node,node);
been[node]=1;
for(auto k:adj[node])
if(been[k.first]==0)create_centroid(k.first);
}
long long mini[nmax];
int inv[nmax*2];
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;i++)
{
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
dfs(0,0,0,0);
for(int h=1;(1<<h)<=t;h++)
for(int i=1;i+(1<<h)-1<=t;i++)
table[h][i]=min(table[h-1][i],table[h-1][i+(1<<(h-1))]);
for(int h=1;h<=t;h++)
{
while((1<<inv[h])+(1<<inv[h])<h)inv[h]++;
}
create_centroid(0);
for(int i=0;i<n;i++)mini[i]=inf;
}
pair<int/*height*/,int/*node*/> ask_min(int le,int ri)
{
int sz=inv[ri-le+1];
return min(table[sz][le],table[sz][ri-(1<<sz)+1]);
}
int LCA(int u,int v)
{
return ask_min(min(in[u],in[v]),max(out[u],out[v])).second;
}
long long dist(int u,int v)
{
return depth[u]+depth[v]-2*depth[LCA(u,v)];
}
void mark(int node)
{
for(auto k:centroid_paths[node])
mini[k]=min(mini[k],dist(k,node));
}
long long closest(int node)
{
long long ret=inf;
for(auto k:centroid_paths[node])
ret=min(ret,mini[k]+dist(k,node));
return ret;
}
void unmark(int node)
{
for(auto k:centroid_paths[node])
mini[k]=inf;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0;i<S;i++)
mark(X[i]);
long long ret=inf;
for(int j=0;j<T;j++)
ret=min(ret,closest(Y[j]));
for(int i=0;i<S;i++)
unmark(X[i]);
return ret;
}
Compilation message
factories.cpp:21:12: warning: 'Qy' defined but not used [-Wunused-variable]
21 | static int Qy[MAX_N];
| ^~
factories.cpp:20:12: warning: 'Qx' defined but not used [-Wunused-variable]
20 | static int Qx[MAX_N];
| ^~
factories.cpp:18:12: warning: 'Y' defined but not used [-Wunused-variable]
18 | static int Y[MAX_SUM_ST];
| ^
factories.cpp:17:12: warning: 'X' defined but not used [-Wunused-variable]
17 | static int X[MAX_SUM_ST];
| ^
factories.cpp:16:12: warning: 'T' defined but not used [-Wunused-variable]
16 | static int T[MAX_N];
| ^
factories.cpp:15:12: warning: 'S' defined but not used [-Wunused-variable]
15 | static int S[MAX_N];
| ^
factories.cpp:14:32: warning: 'D' defined but not used [-Wunused-variable]
14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
| ^
factories.cpp:14:22: warning: 'B' defined but not used [-Wunused-variable]
14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
| ^
factories.cpp:14:12: warning: 'A' defined but not used [-Wunused-variable]
14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
| ^
factories.cpp:13:15: warning: 'Q' defined but not used [-Wunused-variable]
13 | static int N, Q;
| ^
factories.cpp:13:12: warning: 'N' defined but not used [-Wunused-variable]
13 | static int N, Q;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
24320 KB |
Output is correct |
| 2 |
Correct |
573 ms |
33656 KB |
Output is correct |
| 3 |
Correct |
707 ms |
33784 KB |
Output is correct |
| 4 |
Correct |
700 ms |
33912 KB |
Output is correct |
| 5 |
Correct |
681 ms |
34168 KB |
Output is correct |
| 6 |
Correct |
381 ms |
33616 KB |
Output is correct |
| 7 |
Correct |
708 ms |
33912 KB |
Output is correct |
| 8 |
Correct |
713 ms |
33880 KB |
Output is correct |
| 9 |
Correct |
689 ms |
34168 KB |
Output is correct |
| 10 |
Correct |
362 ms |
33544 KB |
Output is correct |
| 11 |
Correct |
701 ms |
33784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24192 KB |
Output is correct |
| 2 |
Incorrect |
3747 ms |
191212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
24320 KB |
Output is correct |
| 2 |
Correct |
573 ms |
33656 KB |
Output is correct |
| 3 |
Correct |
707 ms |
33784 KB |
Output is correct |
| 4 |
Correct |
700 ms |
33912 KB |
Output is correct |
| 5 |
Correct |
681 ms |
34168 KB |
Output is correct |
| 6 |
Correct |
381 ms |
33616 KB |
Output is correct |
| 7 |
Correct |
708 ms |
33912 KB |
Output is correct |
| 8 |
Correct |
713 ms |
33880 KB |
Output is correct |
| 9 |
Correct |
689 ms |
34168 KB |
Output is correct |
| 10 |
Correct |
362 ms |
33544 KB |
Output is correct |
| 11 |
Correct |
701 ms |
33784 KB |
Output is correct |
| 12 |
Correct |
18 ms |
24192 KB |
Output is correct |
| 13 |
Incorrect |
3747 ms |
191212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
