| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 684026 | nguyentunglam | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e6 + 10;
int st[N], ed[N], h[N], vtx[N << 1], f[22][N << 1], num[N], a[N << 1];
long long d[N], nearest[3][N], res;
int cnt, timer;
bool mark1[N], mark2[N];
vector<pair<int, int> > adj[N];
vector<int> ke[N];
void dfs(int u) {
st[u] = ++timer;
vtx[++cnt] = u;
num[u] = cnt;
for(auto [v, w] : adj[u]) if (!st[v]) {
h[v] = h[u] + 1; d[v] = d[u] + w;
dfs(v);
vtx[++cnt] = u;
}
ed[u] = timer;
}
int lca(int u, int v) {
int l = num[u], r = num[v];
if (l > r) swap(l, r);
int k = log2(r - l + 1);
int x = f[k][l], y = f[k][r - (1 << k) + 1];
return h[x] < h[y] ? x : y;
}
void solve(int u) {
nearest[1][u] = nearest[2][u] = 1e16;
if (mark1[u]) nearest[1][u] = d[u];
if (mark2[u]) nearest[2][u] = d[u];
for(int v : ke[u]) {
solve(v);
for(int j = 1; j <= 2; j++) nearest[j][u] = min(nearest[j][u], nearest[j][v]);
}
res = min(res, nearest[1][u] + nearest[2][u] - 2LL * d[u]);
}
void Init (int n, int a[], int b[], int d[]) {
for(int i = 0; i <= n - 2; i++) {
adj[a[i]].emplace_back(b[i], d[i]);
adj[b[i]].emplace_back(a[i], d[i]);
}
dfs(0);
for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
f[j][i] = h[x] < h[y] ? x : y;
}
}
long long Query(int s, int x[], int t, int y[]) {
res = 1e16;
int k = 0;
for(int i = 0; i < s; i++) a[++k] = x[i];
for(int i = 0; i < t; i++) a[++k] = y[i];
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
stack<int> S;
a[0] = a[k];
for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
k <<= 1;
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
S.push(a[1]);
for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
while (ed[S.top()] < st[a[i]]) S.pop();
ke[S.top()].push_back(a[i]);
S.push(a[i]);
}
solve(a[1]);
for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
return res;
}
int main() {
#define task ""
cin.tie(0) -> sync_with_stdio(0);
if (fopen ("task.inp", "r")) {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
}
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int n, q; cin >> n >> q;
for(int i = 1; i < n; i++) {
int u, v, d; cin >> u >> v >> d;
adj[u].emplace_back(v, d);
adj[v].emplace_back(u, d);
}
dfs(0);
for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
f[j][i] = h[x] < h[y] ? x : y;
}
while (q--) {
res = 1e16;
int s, t; cin >> s >> t;
for(int i = 1; i <= s; i++) cin >> a[i], mark1[a[i]] = 1;
for(int i = s + 1; i <= s + t; i++) cin >> a[i], mark2[a[i]] = 2;
int k = s + t;
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
stack<int> S;
a[0] = a[k];
for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
k <<= 1;
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
S.push(a[1]);
for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
while (ed[S.top()] < st[a[i]]) S.pop();
ke[S.top()].push_back(a[i]);
S.push(a[i]);
}
solve(a[1]);
cout << res << endl;
for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
}
}