제출 #921894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921894		falaz	공장들 (JOI14_factories)	C++17	100 / 100	5819 ms	293220 KiB

factories

//#include "factories.h"
#include <bits/stdc++.h> 
using namespace std;

const int M = 5e5 + 1;
int st[M], fn[M], t, cnt, n , loc[M], ql, qr, lg[2 * M];
vector<pair<int, long long>> adj[M];
long long dis[M], seg[2][M << 2];
pair<int, int> par[20][M << 1];

void dfs(int v, int p, long long d1, int h) {
	dis[v] = d1;
	st[v] = t++;
	loc[v] = cnt;
	par[0][cnt++] = {h, v};
	for (auto u : adj[v]) 
		if (u.first != p) { 
			dfs(u.first, v, d1 + 1ll * u.second, h + 1);
			par[0][cnt++] = {h, v};
		}
	fn[v] = t - 1;
	return;
}

void update(int v, int l, int r, int i, long long k, bool g) {
	if (l == r) {
		seg[g][v] = k;
		return;
	}
	int mid = (r + l) >> 1;
	if (i <= mid) {
		if (l == mid) 
			seg[g][v << 1] = k;
		else
			update(v << 1, l, mid, i, k, g);
	}
	else {
		if (mid + 1 == r) 
			seg[g][v << 1 | 1] = k;
		else
			update(v << 1 | 1, mid + 1, r, i, k, g);
	}
	seg[g][v] = min(seg[g][v << 1], seg[g][v << 1 | 1]);
}

long long get(int v, int l, int r, bool g) {
	if (ql <= l && r <= qr) 
		return seg[g][v];
	if (r < ql || qr < l) 
		return 1e18 ;
	int mid = (r + l) >> 1;
	long long a = 1e18, b = 1e18; 
	if (ql <= l && mid <= qr) 
		a = seg[g][v << 1];
	else if (mid < ql || qr < l)
		a = a;
	else
		a = get(v << 1, l, mid, g);
	if (ql <= mid + 1 && r <= qr)
		b = seg[g][v << 1 | 1];
	else if (r < ql || qr < mid + 1)
		b = b;
	else
		b = get(v << 1 | 1, mid + 1, r, g);
	return min(a, b);
}

void rem(int v, int l, int r, int i, bool g) {
	seg[g][v] = 1e18 ;
	if (l == r) 
		return;
	int mid = (r + l) >> 1;
	if (i <= mid) {
		if (l == mid) {
			seg[g][v << 1] = 1e18;
			return;
		}
		rem(v << 1, l, mid, i, g);
	}
	else {
		if (mid + 1 == r) {
			seg[g][v << 1 | 1] = 1e18;
			return;
		}
		rem(v << 1 | 1,  mid + 1, r, i, g);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0, 0, 0);
	for (int i = 2; i < 2 * n; i++)
		lg[i] = lg[i / 2] + 1;
	queue<pair<int, pair<int, int>>> q;
	q.push({1, {0, n - 1}});
	while (q.size()) {
		int v = q.front().first, l = q.front().second.first, r = q.front().second.second;
		seg[0][v] = seg[1][v] = 1e18;
		q.pop();
		if (l != r) {
			int mid = (l + r) >> 1;
			q.push({v << 1, {l, mid}});
			q.push({v << 1 | 1, {mid + 1, r}});
		}
	}
	for (int i = 1; i < 20; i++) 
		for (int j = 0; j + (1 << i) < 2 * n; j++) 
			par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pair<int, int>> sv;
	for (int i = 0; i < S; i++) {
		update(1, 0, n - 1, st[X[i]], dis[X[i]], 0);
		sv.push_back({st[X[i]], X[i]});
	}
	for (int i = 0; i < T; i++) {
		update(1, 0, n - 1, st[Y[i]], dis[Y[i]], 1);
		sv.push_back({st[Y[i]], Y[i]});
	}
	sort(sv.begin(), sv.end());
	long long ans = 1e18 ;
	for (int i = 0; i < int(sv.size()); i++) {
		int v = sv[i].second;
		ql = st[v];
		qr = fn[v];
		long long f = get(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (2ll * dis[v]);
		ans = min(ans, f);
		if (i < int(sv.size()) - 1) {
			int vv = sv[i].second, uu = sv[i + 1].second;
			if (loc[vv] > loc[uu])
				swap(vv, uu);
			int SV = loc[vv], SU = loc[uu], LG = lg[SU - SV + 1];
			pair<int, int> lca = min(par[LG][SV], par[LG][SU - (1 << LG) + 1]);
			v = lca.second;
			ql = st[v];
			qr = fn[v];
			f = get(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (2ll * dis[v]);
	 		ans = min(ans, f);
		}
	}
	for (int i = 0; i < S; i++) 
		rem(1, 0, n - 1, st[X[i]], 0);
	for (int i = 0; i < T; i++)
		rem(1, 0, n - 1, st[Y[i]], 1);
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67