이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 5e5 + 5;
const int LOGN = 20;
const i64 oo64 = 1e18;
#define ALL(a) (a).begin(), (a).end()
int N, Q;
vector<pii> adj[MAXN];
int up[MAXN][LOGN];
int depth[MAXN];
int tin[MAXN];
int tout[MAXN];
int tdfs = 0;
i64 dist[MAXN];
i64 dp[MAXN][2];
vector<int> g[MAXN];
void DFS(int u, int p) {
depth[u] = depth[p] + 1;
tin[u] = ++tdfs;
up[u][0] = p;
for(int i = 1; i < LOGN; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for(auto [v, w] : adj[u]) {
if(v == p) continue;
dist[v] = dist[u] + w;
DFS(v, u);
}
tout[u] = tdfs;
}
bool inside(int u, int v) {
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int LCA(int u, int v) {
if(depth[u] != depth[v]) {
if(depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
for(int i = 0; (1 << i) <= k; i++) {
if(k >> i & 1)
u = up[u][i];
}
}
if(u == v) return u;
int k = 31 - __builtin_clz(depth[u]);
for(int i = k; i >= 0; i--) {
if(up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
i64 get_dist(int u, int v) {
return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
int u = A[i];
int v = B[i];
int w = D[i];
u++;
v++;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for(int i = 1; i <= N; i++) dp[i][0] = dp[i][1] = oo64;
DFS(1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> ver;
for(int i = 0; i < S; i++) {
int u = X[i];
u++;
dp[u][0] = dist[u];
ver.emplace_back(u);
}
for(int i = 0; i < T; i++) {
int u = Y[i];
u++;
dp[u][1] = dist[u];
ver.emplace_back(u);
}
sort(ALL(ver), [&](const int a, const int b) {
return tin[a] < tin[b];
});
ver.resize(unique(ALL(ver)) - ver.begin());
int M = ver.size();
for(int i = 0; i < M; i++)
ver.emplace_back(LCA(ver[i], ver[i + 1]));
sort(ALL(ver), [&](const int a, const int b) {
return tin[a] < tin[b];
});
ver.resize(unique(ALL(ver)) - ver.begin());
stack<int> st;
for(int x : ver) {
while(!st.empty() and inside(st.top(), x) == false)
st.pop();
if(!st.empty()) {
int u = st.top();
g[u].emplace_back(x);
}
st.emplace(x);
}
reverse(ALL(ver));
for(int x : ver) {
for(int v : g[x]) {
for(int j = 0; j < 2; j++)
dp[x][j] = min(dp[x][j], dp[v][j]);
}
}
i64 ans = oo64;
for(int x : ver) {
ans = min(ans, dp[x][0] + dp[x][1] - 2 * dist[x]);
}
for(int x : ver) {
g[x].clear();
dp[x][0] = dp[x][1] = oo64;
}
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... |