이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
int n;
vector<pair<int, int> > adj[500000];
int iscentroid[500000];
int sz[500000];
ll closest[500000];
pair<int, ll> mycentroids[500000][19];
int findsz(int a, int p = -1)
{
sz[a] = 1;
for (auto b : adj[a])
{
if (b.first != p && !iscentroid[b.first]) sz[a] += findsz(b.first, a);
}
return sz[a];
}
ll len = 0;
void dfslen(int a, int c, int p = -1, ll len = 0)
{
mycentroids[a][iscentroid[c]-1] = { c, len };
D("%d belongs to %d, dis %lld\n", a, c, len);
for (auto b : adj[a])
{
if (!iscentroid[b.first] && b.first != p)
{
dfslen(b.first, c, a, len+b.second);
}
}
}
void findcentroid(int a, int upto = 1, int above = 0, int p = -1)
{
int sumchildren = above+1;
pair<int, int> mxchild = { 0, 0 };
for (auto b : adj[a])
{
if (b.first != p && !iscentroid[b.first])
{
mxchild = max(mxchild, { sz[b.first], b.first } );
sumchildren += sz[b.first];
}
}
if (mxchild.first <= (sumchildren)/2)
{
// is a centroid
iscentroid[a] = upto;
dfslen(a, a);
if (p != -1 && !iscentroid[p]) findsz(p, a);
for (auto b : adj[a])
{
if (!iscentroid[b.first]) findcentroid(b.first, upto+1);
}
return;
}
findcentroid(mxchild.second, upto, sumchildren-mxchild.first, a);
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < n-1; i++)
{
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
for (int i = 0; i < n; i++) fill_n(mycentroids[i], 19, make_pair(0, 1e15));
findsz(0);
findcentroid(0);
fill_n(closest, n, 1e15);
}
ll Query(int s, int x[], int t, int y[])
{
ll ans = 1e15;
for (int i = 0; i < s; i++) for (int j = 0; j < 19; j++)
{
closest[mycentroids[x[i]][j].first] = min(closest[mycentroids[x[i]][j].first], mycentroids[x[i]][j].second);
}
for (int i = 0; i < t; i++) for (int j = 0; j < 19; j++)
{
ans = min(ans, closest[mycentroids[y[i]][j].first]+mycentroids[y[i]][j].second);
}
for (int i = 0; i < s; i++) for (int j = 0; j < 19; j++)
{
closest[mycentroids[x[i]][j].first] = 1e15;
}
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... |