#include<bits/stdc++.h>
#include "factories.h"
using namespace std ;
const int LG = 20 , mx = 5e5 + 10 ;
const long long INF = 1e18 ;
set<pair<int,long long> > g[mx] ;
int n , m , p[mx][LG] , depth[mx] , siz[mx] , parent[mx] ;
long long ans[mx] , cost[mx] ;
void dfs(int u , int par , int deep = 0 , long long cst = 0)
{
depth[u] = deep , cost[u] = cst , p[u][0] = par ;
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
dfs(v.first,u,deep+1,cst+v.second) ;
}
}
int comp ;
void visit(int u , int par)
{
++comp , siz[u] = 1;
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
visit(v.first,u) ;
siz[u] += siz[v.first] ;
}
}
int find_centroid(int u , int par)
{
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
if(siz[v.first] > (comp/2))
{
return find_centroid(v.first,u) ;
}
}
return u ;
}
void decompose(int u , int par)
{
comp = 0 , visit(u,u) ;
int centroid = find_centroid(u,u) ;
parent[centroid] = par ;
for(pair<int,long long> v : g[centroid])
{
g[v.first].erase({centroid,v.second}) ;
decompose(v.first,centroid) ;
}
g[centroid].clear() ;
}
int lca(int u , int v)
{
if(depth[u] < depth[v]) swap(u,v) ;
for(int i = LG - 1 ; i >= 0 ; --i)
{
if((depth[u] - (1<<i))>=depth[v]) u = p[u][i] ;
}
if(u==v) return u ;
for(int i = LG - 1 ; i >= 0 ; --i)
{
if(p[u][i] != -1 && p[u][i] != p[v][i])
{
u = p[u][i] , v = p[v][i] ;
}
}
return p[u][0] ;
}
long long dist(int u , int v)
{
return cost[u] + cost[v] - 2*cost[lca(u,v)] ;
}
void update(int u)
{
int x = u ;
while(1)
{
ans[x] = min(ans[x],dist(x,u)) ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
}
void clean(int u)
{
int x = u ;
while(1)
{
ans[x] = INF ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
}
long long query(int u)
{
int x = u ;
long long res = INF ;
while(1)
{
res = min(res,ans[x] + dist(x,u)) ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
return res ;
}
void Init(int N , int A[] , int B[] , int D[])
{
n = N ;
for(int i = 0 ; i < (N-1) ; ++i)
{
g[A[i]].insert({B[i],D[i]}) ;
g[B[i]].insert({A[i],D[i]}) ;
}
memset(p,-1,sizeof(p)) ;
dfs(0,0) ;
decompose(0,-1) ;
for(int j = 1 ; j < LG ; ++j)
{
for(int i = 0 ; i < n ; ++i)
{
if(p[i][j-1] != -1)
{
p[i][j] = p[p[i][j-1]][j-1] ;
}
}
}
for(int i = 0 ; i < n ; ++i) ans[i] = INF ;
}
long long Query(int S , int X[] , int T , int Y[])
{
long long res = INF ;
for(int i = 0 ; i < S ; ++i) update(X[i]) ;
for(int i = 0 ; i < T ; ++i)
{
res = min(res,query(Y[i])) ;
}
for(int i = 0 ; i < S ; ++i) clean(X[i]) ;
return res ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
63596 KB |
Output is correct |
2 |
Correct |
1164 ms |
81388 KB |
Output is correct |
3 |
Correct |
2025 ms |
81692 KB |
Output is correct |
4 |
Correct |
1988 ms |
81524 KB |
Output is correct |
5 |
Correct |
2444 ms |
81836 KB |
Output is correct |
6 |
Correct |
468 ms |
81260 KB |
Output is correct |
7 |
Correct |
2003 ms |
81372 KB |
Output is correct |
8 |
Correct |
2119 ms |
81616 KB |
Output is correct |
9 |
Correct |
2376 ms |
81740 KB |
Output is correct |
10 |
Correct |
454 ms |
81388 KB |
Output is correct |
11 |
Correct |
2053 ms |
81436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
63212 KB |
Output is correct |
2 |
Correct |
3807 ms |
170752 KB |
Output is correct |
3 |
Execution timed out |
8077 ms |
169084 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
63596 KB |
Output is correct |
2 |
Correct |
1164 ms |
81388 KB |
Output is correct |
3 |
Correct |
2025 ms |
81692 KB |
Output is correct |
4 |
Correct |
1988 ms |
81524 KB |
Output is correct |
5 |
Correct |
2444 ms |
81836 KB |
Output is correct |
6 |
Correct |
468 ms |
81260 KB |
Output is correct |
7 |
Correct |
2003 ms |
81372 KB |
Output is correct |
8 |
Correct |
2119 ms |
81616 KB |
Output is correct |
9 |
Correct |
2376 ms |
81740 KB |
Output is correct |
10 |
Correct |
454 ms |
81388 KB |
Output is correct |
11 |
Correct |
2053 ms |
81436 KB |
Output is correct |
12 |
Correct |
39 ms |
63212 KB |
Output is correct |
13 |
Correct |
3807 ms |
170752 KB |
Output is correct |
14 |
Execution timed out |
8077 ms |
169084 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |