#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 up[20][nmax];
void dfs(int node,int par,int h,long long sum)
{
height[node]=h;
depth[node]=sum;
up[0][node]=par;
for(int i=1;i<20;i++)up[i][node]=up[i-1][up[i-1][node]];
for(auto k:adj[node])
if(k.first!=par)
dfs(k.first,node,h+1,sum+k.second);
}
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];
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);
create_centroid(0);
for(int i=0;i<n;i++)mini[i]=inf;
}
int LCA(int u,int v)
{
if(height[u]<height[v])swap(u,v);
for(int i=19;i>=0;i--)
if(height[u]-(1<<i)>=height[v])u=up[i][u];
if(u==v)return u;
for(int i=19;i>=0;i--)
if(up[i][u]!=up[i][v])u=up[i][u],v=up[i][v];
return up[0][u];
}
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 |
40 ms |
24320 KB |
Output is correct |
| 2 |
Correct |
1255 ms |
33528 KB |
Output is correct |
| 3 |
Correct |
2245 ms |
34552 KB |
Output is correct |
| 4 |
Correct |
2174 ms |
34040 KB |
Output is correct |
| 5 |
Correct |
2529 ms |
34244 KB |
Output is correct |
| 6 |
Correct |
470 ms |
33792 KB |
Output is correct |
| 7 |
Correct |
2172 ms |
34168 KB |
Output is correct |
| 8 |
Correct |
2303 ms |
34064 KB |
Output is correct |
| 9 |
Correct |
2524 ms |
34296 KB |
Output is correct |
| 10 |
Correct |
473 ms |
33912 KB |
Output is correct |
| 11 |
Correct |
2160 ms |
34040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24192 KB |
Output is correct |
| 2 |
Correct |
5941 ms |
144376 KB |
Output is correct |
| 3 |
Execution timed out |
8071 ms |
162128 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
24320 KB |
Output is correct |
| 2 |
Correct |
1255 ms |
33528 KB |
Output is correct |
| 3 |
Correct |
2245 ms |
34552 KB |
Output is correct |
| 4 |
Correct |
2174 ms |
34040 KB |
Output is correct |
| 5 |
Correct |
2529 ms |
34244 KB |
Output is correct |
| 6 |
Correct |
470 ms |
33792 KB |
Output is correct |
| 7 |
Correct |
2172 ms |
34168 KB |
Output is correct |
| 8 |
Correct |
2303 ms |
34064 KB |
Output is correct |
| 9 |
Correct |
2524 ms |
34296 KB |
Output is correct |
| 10 |
Correct |
473 ms |
33912 KB |
Output is correct |
| 11 |
Correct |
2160 ms |
34040 KB |
Output is correct |
| 12 |
Correct |
20 ms |
24192 KB |
Output is correct |
| 13 |
Correct |
5941 ms |
144376 KB |
Output is correct |
| 14 |
Execution timed out |
8071 ms |
162128 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
