| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 25297 | dotorya | Factories (JOI14_factories) | C++14 | 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 <algorithm>
#include <stdlib.h>
#include <vector>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
bool dchk[500050];
int dep[500050];
int lr[500050][2];
ll par[500050][20][2];
int tus;
vector <pll> conn[500050];
void DFS(int n) {
dchk[n] = true;
lr[n][0] = ++tus;
for (auto it : conn[n]) {
if (dchk[it.second]) continue;
par[it.second][0][0] = n, par[it.second][0][1] = it.first;
for (int i = 1; i <= 18; i++) {
int tp = par[it.second][i - 1][0];
par[it.second][i][0] = par[tp][i - 1][0];
par[it.second][i][1] = par[it.second][i - 1][1] + par[tp][i - 1][1];
}
dep[it.second] = dep[n] + 1;
DFS(it.second);
}
lr[n][1] = tus;
}
pll lca(int a, int b) {
ll rv = 0;
if (dep[a] > dep[b]) swap(a, b);
int c = dep[b] - dep[a];
for (int i = 18; i >= 0; i--) {
if (c & (1 << i)) {
rv += par[b][i][1];
b = par[b][i][0];
}
}
if (a == b) return pll(rv, a);
for (int i = 18; i >= 0; i--) {
if (par[a][i][0] != par[b][i][0]) {
rv += par[a][i][1];
rv += par[b][i][1];
a = par[a][i][0];
b = par[b][i][0];
}
}
rv += par[a][0][1];
rv += par[b][0][1];
return pll(rv, par[a][0][0]);
}
void Init(int N, int A[], int B[], int D[]) {
int i, j;
for (i = 0; i <= N - 2; i++) {
conn[A[i]].emplace_back(D[i], B[i]);
conn[B[i]].emplace_back(D[i], A[i]);
}
tus = 0;
DFS(0);
}
class Node {
public:
ll mn, v;
Node() {
*this = Node(0, 0);
}
Node(ll mn, ll v) : mn(mn), v(v) {}
};
Node indt[1100000];
void update(int st, int en, int S, int E, int n, ll v) {
if (st > en) return;
if (st == S && en == E) {
indt[n].mn += v;
indt[n].v += v;
return;
}
int M = (S + E) / 2;
update(st, min(en, M), S, M, 2 * n, v);
update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
}
ll qans;
vector <int> Vv;
vector <int> Vv2;
vector <pll> conn2[500050];
vector <pll> son2[500050];
ll dis[500050];
int lr2[500050][2];
int tchk[500050];
void DFS2(int n) {
dchk[n] = true;
lr2[n][0] = ++tus;
for (auto it : conn2[n]) {
if (dchk[it.second]) continue;
son2[n].push_back(it);
dis[it.second] = dis[n] + it.first;
DFS2(it.second);
}
lr2[n][1] = tus;
}
void DFS3(int n) {
if (tchk[n] == 1) qans = min(qans, indt[1].mn);
for (auto it : son2[n]) {
indt[1].mn += it.first, indt[1].v += it.first;
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
DFS3(it.second);
indt[1].mn -= it.first, indt[1].v -= it.first;
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, 2 * it.first);
}
}
long long Query(int S, int X[], int T, int Y[]) {
Vv.reserve(2 * (S + T));
Vv2.reserve(S + T);
int i, j;
for (i = 0; i < S; i++) Vv.push_back(X[i]);
for (i = 0; i < T; i++) Vv.push_back(Y[i]);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
for (auto it : Vv2) Vv.push_back(it);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
Vv.erase(unique(all(Vv)), Vv.end());
for (auto it : Vv) tchk[it] = 0;
for (i = 0; i < S; i++) tchk[X[i]] = 1;
for (i = 0; i < T; i++) tchk[Y[i]] = -1;
for (i = 0; i + 1 < Vv.size(); i++) {
int x = Vv[i];
int y = Vv[i + 1];
x = lca(x, y).second;
pll u = lca(x, y);
conn2[x].emplace_back(u.first, y);
conn2[y].emplace_back(u.first, x);
}
for (i = 0; i < Vv.size(); i++) {
dchk[Vv[i]] = false;
dis[Vv[i]] = 0;
}
tus = 0;
DFS2(Vv[0]);
for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
for (i = 0; i < Vv.size(); i++) {
ll v = dis[Vv[i]];
if (tchk[Vv[i]] != -1) v = LL_INF;
update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
}
update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
qans = LL_INF;
DFS3(Vv[0]);
for (auto it : Vv) {
conn2[it].clear();
son2[it].clear();
}
Vv.clear();
Vv2.clear();
return qans;
}