oj.uz

Submission #958957

# Submission time Handle Problem Language Result Execution time Memory
958957 2024-04-07T09:43:07 Z Pring Factories (JOI14_factories) C++17
100 / 100
 3779 ms 236156 KB 
#include <bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx","popcnt","sse4","abm")
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 31 ms 127836 KB Output is correct
2 Correct 609 ms 133032 KB Output is correct
3 Correct 712 ms 132856 KB Output is correct
4 Correct 620 ms 133120 KB Output is correct
5 Correct 470 ms 133228 KB Output is correct
6 Correct 485 ms 132852 KB Output is correct
7 Correct 696 ms 133108 KB Output is correct
8 Correct 622 ms 133620 KB Output is correct
9 Correct 466 ms 133316 KB Output is correct
10 Correct 464 ms 133020 KB Output is correct
11 Correct 717 ms 132976 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 125676 KB Output is correct
2 Correct 1603 ms 203972 KB Output is correct
3 Correct 2563 ms 210716 KB Output is correct
4 Correct 1038 ms 208284 KB Output is correct
5 Correct 1923 ms 232632 KB Output is correct
6 Correct 2805 ms 210936 KB Output is correct
7 Correct 1729 ms 159104 KB Output is correct
8 Correct 812 ms 158544 KB Output is correct
9 Correct 1254 ms 162944 KB Output is correct
10 Correct 1872 ms 159520 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 127836 KB Output is correct
2 Correct 609 ms 133032 KB Output is correct
3 Correct 712 ms 132856 KB Output is correct
4 Correct 620 ms 133120 KB Output is correct
5 Correct 470 ms 133228 KB Output is correct
6 Correct 485 ms 132852 KB Output is correct
7 Correct 696 ms 133108 KB Output is correct
8 Correct 622 ms 133620 KB Output is correct
9 Correct 466 ms 133316 KB Output is correct
10 Correct 464 ms 133020 KB Output is correct
11 Correct 717 ms 132976 KB Output is correct
12 Correct 18 ms 125676 KB Output is correct
13 Correct 1603 ms 203972 KB Output is correct
14 Correct 2563 ms 210716 KB Output is correct
15 Correct 1038 ms 208284 KB Output is correct
16 Correct 1923 ms 232632 KB Output is correct
17 Correct 2805 ms 210936 KB Output is correct
18 Correct 1729 ms 159104 KB Output is correct
19 Correct 812 ms 158544 KB Output is correct
20 Correct 1254 ms 162944 KB Output is correct
21 Correct 1872 ms 159520 KB Output is correct
22 Correct 2513 ms 219516 KB Output is correct
23 Correct 2498 ms 225848 KB Output is correct
24 Correct 2810 ms 229568 KB Output is correct
25 Correct 3126 ms 230088 KB Output is correct
26 Correct 3524 ms 215868 KB Output is correct
27 Correct 2350 ms 236156 KB Output is correct
28 Correct 1635 ms 216924 KB Output is correct
29 Correct 3616 ms 213788 KB Output is correct
30 Correct 3535 ms 213352 KB Output is correct
31 Correct 3779 ms 213688 KB Output is correct
32 Correct 993 ms 168260 KB Output is correct
33 Correct 897 ms 162360 KB Output is correct
34 Correct 1213 ms 159368 KB Output is correct
35 Correct 1221 ms 158960 KB Output is correct
36 Correct 1459 ms 159760 KB Output is correct
37 Correct 1483 ms 159176 KB Output is correct