oj.uz

Submission #958956

# Submission time Handle Problem Language Result Execution time Memory
958956 2024-04-07T09:41:00 Z Pring Factories (JOI14_factories) C++17
100 / 100
 4238 ms 257396 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<bool, bool> pbb;

namespace {
	const int MXN = 500005, LG = 20;
	const ll INF = 3.9e18;
	int n;
	vector<pii> edge[MXN];
	int p[LG][MXN], d[MXN], C;
	pii dfn[MXN];
	ll s[LG][MXN];
	pbb clr[MXN];
	
	struct VSET {
		bitset<MXN> b;
		vector<int> v;

		void clear() {
			for (auto &i : v) b[i] = 0;
			v.clear();
		}

		void insert(int x) {
			if (b[x]) return;
			b[x] = true;
			v.push_back(x);
		}
	} vs;

	void ADD_EDGE(int x, int y, int w) {
		edge[x].push_back(mp(w, y));
		edge[y].push_back(mp(w, x));
	}

	void DFS(int id, int par, int dep) {
		p[0][id] = par;
		d[id] = dep;
		dfn[id].fs = C++;
		for (auto &[w, i] : edge[id]) {
			if (i == par) continue;
			s[0][i] = w;
			DFS(i, id, dep + 1);
		}
		dfn[id].sc = C;
	}

	void INIT() {
		DFS(1, 0, 0);
		FOR(w, 1, LG) {
			FOR(id, 1, n + 1) {
				p[w][id] = p[w - 1][p[w - 1][id]];
				s[w][id] = s[w - 1][id] + s[w - 1][p[w - 1][id]];
			}
		}
	}

	int LEAP(int x, int k) {
		FOR(w, 0, LG) {
			if (k & (1 << w)) x = p[w][x];
		}
		return x;
	}

	int LCA(int x, int y) {
		// debug(x, y);
		if (d[x] < d[y]) swap(x, y);
		x = LEAP(x, d[x] - d[y]);
		if (x == y) {
			// debug(x);
			return x;
		}
		for (int w = LG - 1; w >= 0; w--) {
			if (p[w][x] == p[w][y]) continue;
			x = p[w][x];
			y = p[w][y];
		}
		// debug(p[0][x]);
		return p[0][x];
	}

	ll LEN(int r, int x) {
		int dai = d[x] - d[r];
		ll ans = 0;
		FOR(w, 0, LG) {
			if (dai & (1 << w)) {
				ans += s[w][x];
				x = p[w][x];
			}
		}
		return ans;
	}

	namespace VTREE {
		vector<pli> edge[MXN];
		pll rb[MXN];

		void BUILD(vector<pii> &nd) {
			sort(nd.begin(), nd.end());
			// for (auto [_, i] : nd) cout << i << ' ';
			// cout << endl;
			vector<int> st;
			st.push_back(1);
			for (auto [_, i] : nd) {
				if (i == 1) continue;
				while (st.size()) {
					int p = st.back();
					if (!(dfn[i].sc <= dfn[p].sc)) st.pop_back();
					else break;
				}
				int p = st.back();
				// debug(p, i);
				edge[p].push_back(mp(LEN(p, i), i));
				st.push_back(i);
			}
		}

		ll DFS(int id) {
			// debug(id);
			ll ans = INF;
			rb[id] = mp(INF, INF);
			if (clr[id].fs) rb[id].fs = 0;
			if (clr[id].sc) rb[id].sc = 0;
			for (auto [len, i] : edge[id]) {
				ans = min(ans, DFS(i));
				rb[id].fs = min(rb[id].fs, rb[i].fs + len);
				rb[id].sc = min(rb[id].sc, rb[i].sc + len);
			}
			return min(ans, rb[id].fs + rb[id].sc);
		}

		void CLEAR(vector<pii> &nd) {
			for (auto &[_, i] : nd) {
				edge[i].clear();
			}
		}
	}

	ll QUERY() {
		{
			vector<pii> dist;
			for (auto &i : vs.v) dist.push_back(mp(dfn[i].fs, i));
			sort(dist.begin(), dist.end());
			FOR(i, 1, dist.size()) {
				vs.insert(LCA(dist[i - 1].sc, dist[i].sc));
			}
			vs.insert(1);
		}
		ll ans;
		{
			vector<pii> nd;
			for (auto &i : vs.v) nd.push_back(mp(dfn[i].fs, i));
			VTREE::BUILD(nd);
			ans = VTREE::DFS(1);
			VTREE::CLEAR(nd);
		}
		return ans;
	}
}

void Init(int N, int A[], int B[], int D[]) {
	::n = N;
	FOR(i, 0, N - 1) ADD_EDGE(A[i] + 1, B[i] + 1, D[i]);
	INIT();
}

long long Query(int S, int X[], int T, int Y[]) {
	FOR(i, 0, S) {
		vs.insert(X[i] + 1);
		clr[X[i] + 1].fs = 1;
	}
	FOR(i, 0, T) {
		vs.insert(Y[i] + 1);
		clr[Y[i] + 1].sc = 1;
	}
	ll ans = QUERY();
	for (auto &i : vs.v) {
		clr[i] = mp(false, false);
	}
	vs.clear();
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 79112 KB Output is correct
2 Correct 671 ms 91244 KB Output is correct
3 Correct 806 ms 89180 KB Output is correct
4 Correct 712 ms 87120 KB Output is correct
5 Correct 531 ms 87716 KB Output is correct
6 Correct 524 ms 89192 KB Output is correct
7 Correct 754 ms 87176 KB Output is correct
8 Correct 674 ms 89336 KB Output is correct
9 Correct 544 ms 95528 KB Output is correct
10 Correct 568 ms 93264 KB Output is correct
11 Correct 900 ms 95468 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 82776 KB Output is correct
2 Correct 1764 ms 213052 KB Output is correct
3 Correct 2822 ms 216620 KB Output is correct
4 Correct 1177 ms 213264 KB Output is correct
5 Correct 2021 ms 249940 KB Output is correct
6 Correct 3108 ms 218156 KB Output is correct
7 Correct 2177 ms 118196 KB Output is correct
8 Correct 892 ms 155060 KB Output is correct
9 Correct 1446 ms 161080 KB Output is correct
10 Correct 1983 ms 155044 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 79112 KB Output is correct
2 Correct 671 ms 91244 KB Output is correct
3 Correct 806 ms 89180 KB Output is correct
4 Correct 712 ms 87120 KB Output is correct
5 Correct 531 ms 87716 KB Output is correct
6 Correct 524 ms 89192 KB Output is correct
7 Correct 754 ms 87176 KB Output is correct
8 Correct 674 ms 89336 KB Output is correct
9 Correct 544 ms 95528 KB Output is correct
10 Correct 568 ms 93264 KB Output is correct
11 Correct 900 ms 95468 KB Output is correct
12 Correct 15 ms 82776 KB Output is correct
13 Correct 1764 ms 213052 KB Output is correct
14 Correct 2822 ms 216620 KB Output is correct
15 Correct 1177 ms 213264 KB Output is correct
16 Correct 2021 ms 249940 KB Output is correct
17 Correct 3108 ms 218156 KB Output is correct
18 Correct 2177 ms 118196 KB Output is correct
19 Correct 892 ms 155060 KB Output is correct
20 Correct 1446 ms 161080 KB Output is correct
21 Correct 1983 ms 155044 KB Output is correct
22 Correct 2913 ms 228116 KB Output is correct
23 Correct 2877 ms 227972 KB Output is correct
24 Correct 3191 ms 232332 KB Output is correct
25 Correct 3550 ms 233408 KB Output is correct
26 Correct 4078 ms 223980 KB Output is correct
27 Correct 2775 ms 257396 KB Output is correct
28 Correct 1878 ms 228648 KB Output is correct
29 Correct 4083 ms 227096 KB Output is correct
30 Correct 4238 ms 222304 KB Output is correct
31 Correct 3973 ms 222672 KB Output is correct
32 Correct 1059 ms 174212 KB Output is correct
33 Correct 883 ms 169260 KB Output is correct
34 Correct 1395 ms 165944 KB Output is correct
35 Correct 1313 ms 166004 KB Output is correct
36 Correct 1731 ms 166516 KB Output is correct
37 Correct 1559 ms 166540 KB Output is correct