| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 976309 | saayan007 | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
const char nl = '\n';
using ll = long long;
/* #warning checkconstanst as per subtask */
const int mxN = 5e5L + 10;
const int logN = 20;
vector<pair<int, ll>> adj[mxN];
int n;
int par[mxN][logN + 1], dep[mxN];
ll dist[mxN][logN + 1];
ll check[mxN][mxN];
void dfs(int x, int p) {
for(auto U : adj[x]) {
int y = U.first; ll w = U.second;
if(y == p) continue;
dep[y] = dep[x] + 1;
dist[y][0] = w;
par[y][0] = x;
dfs(y, x);
}
}
/* void Init(int N, int A[], int B[], int D[]) { */
void Init(signed N, signed A[], signed B[], signed D[]) {
n = N;
for(int i = 0; i < N - 1; ++i) {
adj[A[i]].emplace_back(B[i], ll(D[i]));
adj[B[i]].emplace_back(A[i], ll(D[i]));
}
dep[0] = 0;
dist[0][0] = -1;
par[0][0] = -1;
dfs(0, -1);
for(int j = 1; j < logN; ++j) {
for(int i = 0; i < N; ++i) {
if(dep[i] < (1ll << j)) {
par[i][j] = dist[i][j] = -1;
}
else {
par[i][j] = par[par[i][j - 1]][j - 1];
dist[i][j] = dist[i][j - 1] + dist[par[i][j - 1]][j - 1];
}
}
}
}
ll distance(int x, int y) {
ll res = 0;
if(dep[x] < dep[y]) swap(x, y);
ll diff = dep[x] - dep[y];
for(int j = logN - 1; j >= 0; --j) {
if(diff < (1ll << j)) continue;
diff -= (1ll << j);
res += dist[x][j];
x = par[x][j];
}
if(x == y) return res;
for(int j = logN - 1; j >= 0; --j) {
if(par[x][j] == par[y][j]) continue;
res += dist[x][j];
x = par[x][j];
res += dist[y][j];
y = par[y][j];
}
res += dist[x][0];
x = par[x][0];
res += dist[y][0];
y = par[y][0];
assert(x == y);
return res;
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
ll res = 1e18;
for(int i = 0; i < S; ++i) {
int x = X[i];
for(int j = 0; j < T; ++j) {
int y = Y[j];
res = min(res, distance(x, y));
}
}
return res;
}