| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 235052 | Blagojce | 공장들 (JOI14_factories) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5 + 5;
//#include "factories.h"
vector<pii> g[mxn];
int sub[mxn];
bool deleted[mxn];
int n;
int sparse[mxn][20];
ll dist[mxn][20];
void dfs0(int u, int p){
sub[u] = 1;
for(auto e : g[u]){
if(e.st == p || deleted[e.st]) continue;
dfs0(e.st, u);
sub[u] += sub[e.st];
}
}
int dfs1(int u, int p){
for(auto e : g[u]){
if(e.st != p && !deleted[e.st] && sub[e.st] > n / 2){
return dfs1(e.st, u);
}
}
return u;
}
void dfs3(int u, int p, int dep){
for(auto e : g[u]){
if(e.st == p || deleted[e.st]) continue;
dist[e.st][dep] = dist[u][dep] + e.nd;
dfs3(e.st, u, dep);
}
}
int parent[mxn];
ll opt[mxn];
int depth[mxn];
void decompose(int root, int p, int dep){
dfs0(root, root);
n = sub[root];
int centroid = dfs1(root, root);
opt[centroid] = inf;
depth[centroid] = dep;
dfs3(centroid, centroid, dep);
if(root != p) parent[centroid] = p;
else parent[centroid] = centroid;
deleted[centroid] = true;
for(auto u : g[centroid]){
if(deleted[u.st]) continue;
decompose(u.st, centroid, dep + 1);
}
}
void Init(int N, int A[], int B[], int D[]) {
fr(i, 0, N - 1){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
decompose(0, 0, 0);
}
void update(int u){
opt[u] = 0;
int x = u;
while(parent[x] != x){
x = parent[x];
opt[x] = min(opt[x], dist[u][depth[x]]);
}
}
void rupdate(int u){
opt[u] = inf;
int x = u;
while(parent[x] != x){
x = parent[x];
opt[x] = inf;
}
}
ll query(int u){
ll ret = opt[u];
int x = u;
while(parent[x] != x){
x = parent[x];
ret = min(ret, opt[x] + dist[u][depth[x]]);
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
fr(i, 0, S){
update(X[i]);
}
ll ret = inf;
fr(i, 0, T){
ret = min(ret, query(Y[i]));
}
fr(i, 0, S){
rupdate(X[i]);
}
return ret;
}
int main(){
int N, Q;
cin >> N >> Q;
int A[N], B[N], D[N];
fr(i, 0, N - 1){
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
fr(i, 0, Q){
int S, T;
cin >> S >> T;
int X[S], Y[T];
fr(j, 0, S){
cin >> X[j];
}
fr(j, 0, T){
cin >> Y[j];
}
cout << Query(S, X, T, Y)<<endl;
}
}