| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 288218 | kig9981 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<pair<int,int>> adj[500000];
int query_num, root, P[500000], W[500000], num[500000], cnt[500000];
long long V[500000], dist[500000][19];
bool chk[500000];
void reset(int c)
{
W[c]=0;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset(n);
}
int dfs(int c)
{
W[c]=1; V[c]=-1;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=dfs(n);
return W[c];
}
int dfs2(int c, int v)
{
for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return dfs2(n,v);
return c;
}
void dfs3(int c)
{
dist[c][cnt[c]++]=V[c];
for(auto[n,w]: adj[c]) if(!chk[n] && V[n]==-1) {
V[n]=V[c]+w;
dfs3(n);
}
}
int get_centroid(int c)
{
reset(c);
chk[c=dfs2(c,dfs(c))]=true;
dist[c][cnt[c]++]=V[c]=0;
for(auto[n,w]: adj[c]) if(!chk[n]) {
V[n]=w; dfs3(n);
P[get_centroid(n)]=c;
}
return c;
}
void Init(int N, vector<int> A, vector<int> B, vector<int> D)
{
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]);
}
root=get_centroid(0);
}
long long Query(int S, vector<int> X, int T, vector<int> Y)
{
long long ret=0x7fffffffffffffffLL;
int v; ++query_num;
for(int i=0;i<S;i++) {
v=cnt[X[i]];
for(int j=X[i];j!=root;j=P[j]) {
if(num[j]==query_num) V[j]=min(V[j],dist[X[i]][--v]);
else {
num[j]=query_num;
V[j]=dist[X[i]][--v];
}
}
if(num[root]==query_num) V[root]=min(V[root],dist[X[i]][--v]);
else {
num[root]=query_num;
V[root]=dist[X[i]][--v];
}
}
for(int i=0;i<T;i++) {
v=cnt[Y[i]];
for(int j=Y[i];j!=root;j=P[j]) {
v--;
if(num[j]!=query_num) continue;
ret=min(ret,V[j]+dist[Y[i]][v]);
}
ret=min(ret,V[root]+dist[Y[i]][--v]);
}
return ret;
}