| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230951 | vkchudeanhlo | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int max_n = 500005;
const int logn = 20;
const long long inf = 1e18;
vector<pair<int, int>> adj[max_n];
vector<pair<long long, long long>> vtree[max_n];
int up[max_n][logn];
int depth[max_n];
long long dist[max_n];
long long tin[max_n], tout[max_n], timer = 0;
long long dp[max_n];
bool vis[max_n];
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i < logn; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
tin[u] = ++timer;
for (int i = 0; i < (int)adj[u].size(); i++) {
int to = adj[u][i].first;
int w = adj[u][i].second;
if (to != p) {
depth[to] = depth[u] + 1;
dist[to] = dist[u] + w;
dfs(to, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
int tmp = u;
u = v;
v = tmp;
}
for (int i = logn - 1; i >= 0; i--) {
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v]){
u = up[u][i];
}
}
if (u == v) return u;
for (int i = logn - 1; i >= 0; i--) {
if (up[u][i] != -1 && up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
long long getdist(int u, int v) {
int anc = lca(u, v);
return dist[u] + dist[v] - 2 * dist[anc];
}
bool cmp(long long a, long long b) {
return tin[a] < tin[b];
}
bool isanc(long long u, long long v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void init(int n, int a[], int b[], int d[]) {
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(make_pair(b[i], d[i]));
adj[b[i]].push_back(make_pair(a[i], d[i]));
}
for (int i = 0; i < logn; i++) up[0][i] = 0;
depth[0] = 0;
dist[0] = 0;
dfs(0, 0);
for (int i = 0; i < n; i++) dp[i] = -1;
}
long long query(int s, int x[], int t, int y[]) {
vector<long long> spec;
for (int i = 0; i < s; i++) spec.push_back(x[i]);
for (int i = 0; i < t; i++) {
spec.push_back(y[i]);
dp[y[i]] = 0;
}
sort(spec.begin(), spec.end(), cmp);
vector<long long> node = spec;
for (int i = 1; i < (int)spec.size(); i++) {
node.push_back(lca((int)spec[i - 1], (int)spec[i]));
}
sort(node.begin(), node.end(), cmp);
node.erase(unique(node.begin(), node.end()), node.end());
stack<long long> st;
st.push(node[0]);
for (int i = 1; i < (int)node.size(); i++) {
long long u = node[i];
while (!isanc(st.top(), u)) st.pop();
long long v = st.top();
long long d = getdist((int)u, (int)v);
vtree[u].push_back(make_pair(v, d));
vtree[v].push_back(make_pair(u, d));
st.push(u);
}
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
for (int i = 0; i < s; i++) {
pq.push(make_pair(0, x[i]));
}
long long res = inf;
while (!pq.empty()) {
pair<long long, long long> top = pq.top();
pq.pop();
long long d = top.first;
int u = (int)top.second;
if (dp[u] == 0) {
res = d;
break;
}
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < vtree[u].size(); i++){
int to = (int)vtree[u][i].first;
long long w = vtree[u][i].second;
pq.push(make_pair(d + w, to));
}
}
for (int i = 0; i < node.size(); i++){
int u = node[i];
vtree[u].clear();
vis[u] = false;
dp[u] = -1;
}
return res;
}