이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define N 500500
#define pb push_back
struct GRAPH
{
int node;
long long weight;
};
int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N], dp[20][N];
bool visit[N];
vector<GRAPH> g[N];
int get_sz(int u, int p)
{
sz[u] = 1;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
sz[u] += get_sz(x.node, u);
}
return sz[u];
}
int get_centroid(int u, int p, int n)
{
bool ch = (n - sz[u] <= n/2) ? true : false;
int uu = 0;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
if(sz[x.node] > sz[uu])
{
ch = false;
uu = x.node;
}
}
return (ch) ? u : get_centroid(uu, u, n);
}
int build(int u, int p)
{
int c = get_centroid(u, p, get_sz(u, p));
visit[c] = true;
for(auto x : g[c])
{
if(visit[x.node]) continue ;
pa[build(x.node, c)] = c;
}
return c;
}
void dfs(int u, int l)
{
lv[u] = l;
for(auto x : g[u])
{
if(lv[x.node]) continue ;
jmp_node[0][x.node] = u;
jmp_dis[0][x.node] = x.weight;
dfs(x.node, l+1);
}
}
long long get_dis(int u, int v)
{
long long ret = 0;
if(lv[u] < lv[v]) swap(u, v);
for(int i=19 ; i>=0 ; i--)
if(lv[jmp_node[i][u]] >= lv[v])
{
ret += jmp_dis[i][u];
u = jmp_node[i][u];
}
if(u == v) return ret;
for(int i=19 ; i>=0 ; i--)
if(jmp_node[i][u] != jmp_node[i][v])
{
ret += jmp_dis[i][u] + jmp_dis[i][v];
u = jmp_node[i][u], v = jmp_node[i][v];
}
return ret + jmp_dis[0][u] + jmp_dis[0][v];
}
void Init(int n, int u[], int v[], int w[])
{
for(int i=0 ; i<n-1 ; i++)
{
g[u[i]+1].pb({v[i]+1, w[i]});
g[v[i]+1].pb({u[i]+1, w[i]});
}
dfs(1, 1);
build(1, 0);
for(int i=1 ; i<=n ; i++)
{
visit[i] = false;
dis[i] = 1e15;
}
for(int i=1 ; i<20 ; i++)
for(int j=1 ; j<=n ; j++)
{
jmp_node[i][j] = jmp_node[i-1][jmp_node[i-1][j]];
jmp_dis[i][j] = jmp_dis[i-1][j] + jmp_dis[i-1][jmp_node[i-1][j]];
}
}
long long Query(int s, int x[], int t, int y[])
{
long long ans = 1e15;
queue<int> cleaner;
for(int i=0 ; i<s ; i++)
{
int u = x[i]+1;
while(true)
{
if(!visit[u])
{
cleaner.push(u);
visit[u] = true;
}
dis[u] = min(dis[u], get_dis(x[i]+1, u));
u = pa[u];
if(!u) break;
}
}
for(int i=0 ; i<t ; i++)
{
int u = y[i]+1;
while(true)
{
if(visit[u]) ans = min(ans, dis[u] + get_dis(y[i], u));
u = pa[u];
if(!u) break;
}
}
while(!cleaner.empty())
{
dis[cleaner.front()] = 1e15;
visit[cleaner.front()] = true;
cleaner.pop();
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |