| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 40971 | DoanPhuDuc | Factories (JOI14_factories) | C++98 | 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 FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
const int N = 1e5 + 10;
const LL INF = (LL)1e18;
int n, timer = 0, q;
int sz[N], x[N], y[N], c[N], p[N], V[N], headChain[N];
int a[N], b[N], e[N];
LL d[N];
vector <II> adj[N];
struct Node {
LL s0, s1, s2;
Node () {}
Node (LL s0, LL s1, LL s2) : s0(s0), s1(s1), s2(s2) {}
};
struct SegmentTree {
#define m ((l + r) >> 1)
Node st[4 * N];
LL lp[4 * N];
bool rst[4 * N];
void Merge(int k) {
st[k].s0 = min(st[k << 1].s0, st[k << 1 | 1].s0);
st[k].s1 = min(st[k << 1].s1, st[k << 1 | 1].s1);
st[k].s2 = min(st[k << 1].s2, st[k << 1 | 1].s2);
}
void Build(int k, int l, int r) {
lp[k] = INF;
if (l == r) {
int u = V[l];
st[k] = Node(-2LL * d[u], INF, INF);
return;
}
Build(k << 1, l, m);
Build(k << 1 | 1, m + 1, r);
Merge(k);
}
void RS(int k) {
if (rst[k] == false) return;
rst[k] = false;
rst[k << 1] = true; rst[k << 1 | 1] = true;
st[k << 1].s1 = st[k << 1].s2 = INF;
st[k << 1 | 1].s1 = st[k << 1 | 1].s2 = INF;
lp[k << 1] = INF; lp[k << 1 | 1] = INF;
}
void Propagate(int k) {
if (lp[k] >= INF) return;
LL v = lp[k]; lp[k] = INF;
lp[k << 1] = min(lp[k << 1], v); lp[k << 1 | 1] = min(lp[k << 1 | 1], v);
st[k << 1].s1 = min(st[k << 1].s1, v);
st[k << 1 | 1].s1 = min(st[k << 1 | 1].s1, v);
st[k << 1].s2 = min(st[k << 1].s2, st[k << 1].s0 + v);
st[k << 1 | 1].s2 = min(st[k << 1 | 1].s2, st[k << 1 | 1].s0 + v);
}
void Update(int k, int l, int r, int i, int j, LL v) {
if (l > j || r < i) return;
if (i <= l && r <= j) {
lp[k] = min(lp[k], v);
st[k].s1 = min(st[k].s1, v);
st[k].s2 = min(st[k].s2, st[k].s0 + v);
return;
}
RS(k);
Propagate(k);
Update(k << 1, l, m, i, j, v);
Update(k << 1 | 1, m + 1, r, i, j, v);
Merge(k);
}
LL Query(int k, int l, int r, int i, int j) {
if (l > j || r < i) return INF;
if (i <= l && r <= j) return st[k].s2;
RS(k);
Propagate(k);
LL ans = min(Query(k << 1, l, m, i, j), Query(k << 1 | 1, m + 1, r, i, j));
Merge(k);
return ans;
}
void Reset(int k, int l, int r, int i, int j) {
if (l > j || r < i) return;
if (i <= l && r <= j) {
rst[k] = true;
lp[k] = INF;
st[k].s1 = st[k].s2 = INF;
return;
}
RS(k);
Reset(k << 1, l, m, i, j);
Reset(k << 1 | 1, m + 1, r, i, j);
Merge(k);
}
#undef m
} ST;
void DFS(int u) {
c[u] = 1;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue;
p[v] = u; d[v] = d[u] + w;
DFS(v);
c[v] += c[u];
}
}
void HLD(int u, int par) {
sz[par]++; x[u] = ++timer; V[timer] = u;
headChain[u] = par;
int vtx = 0;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue;
if (vtx == 0 || c[vtx] < c[v]) vtx = v;
}
if (vtx != 0) HLD(vtx, par);
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (v == p[u] || v == vtx) continue;
HLD(v, v);
}
y[u] = timer;
}
void Init(int n, int A[], int B[], int D[]) {
REP(i, 0, n - 1) {
int u = A[i], v = B[i], w = D[i];
++u; ++v;
adj[u].push_back(II(v, w));
adj[v].push_back(II(u, w));
}
DFS(1);
HLD(1, 1);
ST.Build(1, 1, n);
}
void Update(int u, LL v) {
int a = 1;
int uChain = headChain[u], aChain = headChain[a];
while (true) {
if (aChain == uChain) {
ST.Update(1, 1, n, x[a], x[u], v);
break;
}
ST.Update(1, 1, n, x[uChain], x[u], v);
u = uChain; u = p[u];
uChain = headChain[u];
}
}
void Reset(int u) {
int a = 1;
int uChain = headChain[u], aChain = headChain[a];
while (true) {
if (aChain == uChain) {
ST.Reset(1, 1, n, x[a], x[u]);
break;
}
ST.Reset(1, 1, n, x[uChain], x[u]);
u = uChain; u = p[u];
uChain = headChain[u];
}
}
LL Query(int u) {
LL w = d[u];
int a = 1;
int uChain = headChain[u], aChain = headChain[a];
LL ans = INF;
while (true) {
if (aChain == uChain) {
ans = min(ans, ST.Query(1, 1, n, x[a], x[u]));
break;
}
ans = min(ans, ST.Query(1, 1, n, x[uChain], x[u]));
u = uChain; u = p[u];
uChain = headChain[u];
}
return ans + w;
}
long long Query(int s, int X[], int t, int Y[]) {
REP(i, 0, s) {
int u = X[i]; ++u;
Update(u, d[u]);
}
LL ans = INF;
REP(i, 0, t) {
int u = Y[i]; ++u;
ans = min(ans, Query(u));
}
REP(i, 0, s) {
int u = X[i]; ++u;
Reset(u);
}
return ans;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d", &n, &q);
FOR(i, 0, n - 2) scanf("%d%d%d", &a[i], &b[i], &e[i]);
Init(n, a, b, e);
while (q--) {
int s, t; scanf("%d%d", &s, &t);
REP(i, 0, s) scanf("%d", &a[i]);
REP(i, 0, t) scanf("%d", &b[i]);
cout << Query(s, a, t, b) << endl;
}
return 0;
}