| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 62142 | Darksinian | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include<bits/stdc++.h>
#include"grader.cpp"
using namespace std;
int n;
int p[5002];
long long l[5002];
long long d[5002];
long long dp2[14][5002];
vector<pair<int,int> > g[5002];
/*
void dfs(int s,int p) {
dp[s][1] = 1e17;
dp[s][2] = 1e17;
if(c[s]) dp[s][c[s]] = 0;
for(auto u : g[s]) {
int u1 = u.first;
if(u1!=p) {
dfs(u1,s);
dp[s][1] = min(dp[s][1],dp[u1][1] + u.second);
dp[s][2] = min(dp[s][2],dp[u1][2] + u.second);
}
}
}
*/
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i =0;i<N;i++){
g[A[i]].push_back({B[i],D[i]});
g[B[i]].push_back({A[i],D[i]});
}
}
void dfs2(int s,int z) {
p[s] = z;
if(s==z) l[s] = 0;
else l[s] = l[z]+1;
for(auto u : g[s]) {
int u1 = u.first;
if(u1!=z) {
d[u1] = d[s] + u.second;
dfs2(u1,s);
}
}
}
int lca(int u,int v) {
if(l[u] > l[v]) swap(u,v);
int ll = l[v] - l[u];
for(int i =0;i<20;i++){
if(ll & (1<<i) ) v = dp2[v][i];
}
if(v == u) return v;
for(int i =20;i>-1;i--){
if(dp2[v][i] != dp2[u][i] && dp2[v][i] !=-1) {
v = dp2[v][i];
u = dp2[u][i];
}
}
return p[v];
}
int pre() {
for(int i =0;i<=20;i++){
for(int j =0;j<n;j++){
if((1<<i) > l[j]) {
dp2[j][i] = -1;
continue;
}
if(!i) dp2[j][i] = p[j];
else dp2[j][i] = dp2[dp2[j][i-1]][i-1];
}
}
}
long long dist(int u, int v) {
return d[u] + d[v] - 2*d[lca(u,v)];
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i =0;i<S;i++) {
//c[X[i]] = 1;
}
for(int i =0;i<T;i++){
//c[Y[i]] = 2;
}
//dfs(0,0);
dfs2(0,0);
pre();
// for(int i =0;i<n;i++) c[i] = 0;
long long ans = 1e18;
for(int i =0;i<S;i++) {
for(int j =0;j<T;j++) ans = min(ans,dist(X[i],Y[j]));
}
return ans;
}