| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 302410 | hexan | 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 "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)
const ll N = 5e5 + 1;
const ll lg = 20;
vector<pair<ll, ll>> g[N];
vector<ll> nxt[N];
ll dist[N];
ll p[N], w[N];
ll root = -1;
ll dfs(ll v, ll pa, ll &c, ll n) {
ll sz = 1;
for(auto to : g[v]) {
if (to.x == pa || p[to.x] != -1) continue;
dist[to.x] = dist[v] + to.y;
sz += dfs(to.x, v, c, n);
}
if (c == -1 && (sz * 2 >= n || pa == -1))
c = v;
return sz;
}
void dec(ll v, ll n) {
for(auto to : g[v]) {
if (p[to.x] == -1) {
ll nx = -1;
dist[to.x] = to.y;
dfs(to.x, -1, nx, n / 2);
nxt[v].push_back(nx);
w[nx] = dist[nx];
p[nx] = v;
dec(nx, n / 2);
}
}
}
ll n;
const ll INF = 1e9;
ll used[2][N], f[2][N], cnt[2][N];
void Init(ll N, ll A[], ll B[], ll D[]) {
n = N;
for(ll i = 0; i < n - 1; i++) {
//--A[i]; --B[i];
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
fill(p, p + N, -1);
dfs(0, -1, root, n);
p[root] = root;
dec(root, N);
for(ll i = 0; i < 2; i++) {
for(ll j = 0; j < n; j++) {
f[i][j] = INF;
}
}
}
ll timer = 0;
ll ans;
void calc(ll v) {
vector<ll> fu = {f[0][v], f[1][v]};
chkmin(ans, fu[0] + fu[1]);
for(ll to : nxt[v]) {
for(ll x : {0, 1}) {
if (timer != used[x][to]) {
used[x][to] = timer;
cnt[x][to] = 0;
f[x][to] = INF;
}
}
chkmin(ans, fu[0] + f[1][to] + w[to]);
chkmin(ans, fu[1] + f[0][to] + w[to]);
chkmin(fu[0], f[0][to] + w[to]);
chkmin(fu[1], f[1][to] + w[to]);
if (cnt[0][to] && cnt[1][to]) {
calc(to);
}
}
}
long long Query(ll S, ll X[], ll T, ll Y[]) {
timer++;
ans = INF * INF;
for(ll i : {0, 1}) {
for(ll j = 0; j < (i == 0 ? S : T); j++) {
ll x;
if (!i) x = X[j];
else x = Y[j];
ll W = 0;
while (1) {
if (used[i][x] != timer) {
used[i][x] = timer;
f[i][x] = INF;
cnt[i][x] = 0;
}
f[i][x] = min(f[i][x], W);
cnt[i][x] = 1;
if (p[x] != x) {
W += w[x];
x = p[x];
} else {
break;
}
}
}
}
calc(root);
return ans;
}