oj.uz

Submission #467065

# Submission time Handle Problem Language Result Execution time Memory
467065 2021-08-21T14:22:50 Z Namnamseo Factories (JOI14_factories) C++17
100 / 100
 4139 ms 178504 KB 
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
using pp=pair<int,int>;
using ll=long long;
const int maxn = int(5e5) + 10;
const ll inf = (1ll<<60);

int n, q;
vector<pp> e[maxn];

int tin[maxn], tout[maxn], nt;
int par[20][maxn];
int dep[maxn];
ll dd[maxn];

void dfs(int x) {
	tin[x] = ++nt;
	for (auto tmp:e[x]) {
		int y, d; tie(y, d) = tmp;
		if (y == par[0][x]) continue;
		par[0][y] = x;
		dep[y] = dep[x]+1;
		dd[y] = dd[x] + d;
		dfs(y);
	}
	tout[x] = nt;
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	for (int df=dep[b]-dep[a], i=18; 0<=i; --i)
		if (1&(df>>i)) b = par[i][b];
	if (a == b) return a;
	for (int i=18; 0<=i; --i) if (par[i][a] != par[i][b])
		a = par[i][a], b = par[i][b];
	return par[0][a];
}

vector<int> vx, vy;
vector<int> va;

bitset<maxn> isx;
bitset<maxn> isy;
vector<pair<int,ll>> te[maxn];
ll dx[maxn], dy[maxn];

pair<ll,ll> tdfs(int x, pair<ll,ll> pd) {
	if (isx[x]) pd.first = 0;
	else if (isy[x]) pd.second = 0;
	ll cx = inf, cy = inf;
	for (auto tmp : te[x]) {
		int y; ll d; tie(y, d) = tmp;
		ll ccx, ccy; tie(ccx, ccy) = tdfs(y, {pd.first+d, pd.second+d});
		cx = min(cx, ccx+d);
		cy = min(cy, ccy+d);
	}
	dx[x] = min(cx, pd.first);
	dy[x] = min(cy, pd.second);
	if (isx[x]) cx = 0;
	else if (isy[x]) cy = 0;
	return {cx, cy};
}

void Init(int n, int A[], int B[], int D[]) {
	for (int i=0; i<n-1; ++i) {
		e[A[i]+1].emplace_back(B[i]+1, D[i]);
		e[B[i]+1].emplace_back(A[i]+1, D[i]);
	}
	dfs(1);
	for (int i=1; i<=18; ++i) for (int j=1; j<=n; ++j) {
		par[i][j] = par[i-1][par[i-1][j]];
	}
}

ll Query(int nx, int X[], int ny, int Y[]) {
    vx.clear(); vx.insert(vx.end(), X, X+nx); for (int &x:vx) ++x;
    vy.clear(); vy.insert(vy.end(), Y, Y+ny); for (int &y:vy) ++y;

	va.resize(nx + ny);
	copy(vx.begin(), vx.end(), va.begin());
	copy(vy.begin(), vy.end(), va.begin()+nx);
	sort(va.begin(), va.end(), [&](const int& a, const int& b) {
		return tin[a] < tin[b];
	});
	for (int i=0; i+1<nx+ny; ++i) {
		int a = va[i], b = va[i+1], l = lca(a, b);
		if (l != a && l != b) va.push_back(l);
	}
	sort(va.begin(), va.end(), [&](const int& a, const int& b) {
		return tin[a] < tin[b];
	});
	va.erase(unique(va.begin(), va.end()), va.end());

	static vector<int> stk; stk.clear();
	for (int x : va) {
		while (!stk.empty()) {
			int p = stk.back();
			if (tin[p] <= tin[x] && tin[x] <= tout[p]) break;
			stk.pop_back();
		}
		if (!stk.empty()) {
			int p = stk.back();
			te[p].emplace_back(x, dd[x]-dd[p]);
		}
		stk.push_back(x);
	}
	for (int x : vx) isx.set(x);
	for (int y : vy) isy.set(y);

	tdfs(va[0], {inf, inf});
	ll ans = inf;
	for (int a : va) ans = min(ans, dx[a]+dy[a]);

	for (int x : va) te[x].clear();
	for (int x : vx) isx.reset(x);
	for (int y : vy) isy.reset(y);

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24524 KB Output is correct
2 Correct 872 ms 42472 KB Output is correct
3 Correct 918 ms 42588 KB Output is correct
4 Correct 866 ms 42496 KB Output is correct
5 Correct 737 ms 42688 KB Output is correct
6 Correct 633 ms 42320 KB Output is correct
7 Correct 903 ms 42352 KB Output is correct
8 Correct 856 ms 42504 KB Output is correct
9 Correct 744 ms 42696 KB Output is correct
10 Correct 630 ms 42316 KB Output is correct
11 Correct 910 ms 42472 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24152 KB Output is correct
2 Correct 1854 ms 128940 KB Output is correct
3 Correct 2519 ms 132564 KB Output is correct
4 Correct 1304 ms 129220 KB Output is correct
5 Correct 2189 ms 172452 KB Output is correct
6 Correct 2619 ms 134820 KB Output is correct
7 Correct 2392 ms 64492 KB Output is correct
8 Correct 1282 ms 64244 KB Output is correct
9 Correct 1668 ms 71360 KB Output is correct
10 Correct 2264 ms 65808 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24524 KB Output is correct
2 Correct 872 ms 42472 KB Output is correct
3 Correct 918 ms 42588 KB Output is correct
4 Correct 866 ms 42496 KB Output is correct
5 Correct 737 ms 42688 KB Output is correct
6 Correct 633 ms 42320 KB Output is correct
7 Correct 903 ms 42352 KB Output is correct
8 Correct 856 ms 42504 KB Output is correct
9 Correct 744 ms 42696 KB Output is correct
10 Correct 630 ms 42316 KB Output is correct
11 Correct 910 ms 42472 KB Output is correct
12 Correct 19 ms 24152 KB Output is correct
13 Correct 1854 ms 128940 KB Output is correct
14 Correct 2519 ms 132564 KB Output is correct
15 Correct 1304 ms 129220 KB Output is correct
16 Correct 2189 ms 172452 KB Output is correct
17 Correct 2619 ms 134820 KB Output is correct
18 Correct 2392 ms 64492 KB Output is correct
19 Correct 1282 ms 64244 KB Output is correct
20 Correct 1668 ms 71360 KB Output is correct
21 Correct 2264 ms 65808 KB Output is correct
22 Correct 3389 ms 145628 KB Output is correct
23 Correct 3216 ms 146828 KB Output is correct
24 Correct 3522 ms 149964 KB Output is correct
25 Correct 3650 ms 153580 KB Output is correct
26 Correct 4059 ms 143544 KB Output is correct
27 Correct 3076 ms 178504 KB Output is correct
28 Correct 2122 ms 144740 KB Output is correct
29 Correct 4139 ms 141880 KB Output is correct
30 Correct 4126 ms 141228 KB Output is correct
31 Correct 4030 ms 141636 KB Output is correct
32 Correct 1467 ms 73224 KB Output is correct
33 Correct 1310 ms 67696 KB Output is correct
34 Correct 2086 ms 63360 KB Output is correct
35 Correct 1981 ms 62952 KB Output is correct
36 Correct 2206 ms 63920 KB Output is correct
37 Correct 2282 ms 63784 KB Output is correct