Submission #958957

#	Time	Username	Problem	Language	Result	Execution time	Memory
958957		Pring	Factories (JOI14_factories)	C++17	100 / 100	3779 ms	236156 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67