Submission #1230842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230842		balls	Factories (JOI14_factories)	C++20	100 / 100	1500 ms	116620 KiB

factories

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

const int MaxN = 5e5 + 7;
const int Log = 20;
int dfn[MaxN], dfst, efn[MaxN], prt[Log][MaxN], dep[MaxN], c[1000005], xyzzzz[500005], cnt, pv;
long long d[MaxN], res;

vector<pair<int, int>> adj[MaxN];

void dfssss(int x, int p) {
	dfn[x] = ++dfst;
	for (auto i : adj[x]) {
		if (i.second == p) {
		    continue;
		}
		dep[dfst + 1] = dep[dfn[x]] + 1;
		d[dfst + 1] = d[dfn[x]] + i.first;
		prt[0][dfst + 1] = dfn[x];
		dfssss(i.second, x);
	}
	efn[dfn[x]] = dfst;
}

pair<long long, long long> dfs(int x) {
	long long s = 1e18, t = 1e18;
	if (xyzzzz[x] == 1) {
	    s = 0;
	}
	if (xyzzzz[x] == 2) {
	    t = 0;
	}
	xyzzzz[x] = 0;
	while (pv < cnt && c[pv] <= efn[x]) {
		int i = c[pv++];
		auto pr = dfs(i);
		s = min(s, pr.first + d[i] - d[x]);
		t = min(t, pr.second + d[i] - d[x]);
	}
	res = min(res, s + t);
	return {s, t};
}

int lca(int s, int e) {
	if (dep[s] < dep[e]) {
	    swap(s, e);
	}
	for (int i = 18; i >= 0; i--) {
		if ((dep[s] - dep[e] >> i) & 1) {
		    s = prt[i][s];
		}
	}
	if (s == e) {
	    return s;
	}
	for (int i = 18; i >= 0; i--) {
		if (prt[i][s] != prt[i][e]) {
		    s = prt[i][s];
		    e = prt[i][e];
		}
	}
	return prt[0][s];
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		adj[A[i]].push_back({D[i], B[i]});
		adj[B[i]].push_back({D[i], A[i]});
	}
	dfssss(0, 0);
	for (int i = 1; i < 19; i++) {
	    for (int j = 1; j <= N; j++) {
	        prt[i][j] = prt[i - 1][prt[i - 1][j]];
	    }
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	cnt = 0;
	for (int i = 0; i < S; i++) {
	    c[cnt] = dfn[X[i]];
	    xyzzzz[c[cnt++]] = 1;
	}
	for (int i = 0; i < T; i++) {
	    c[cnt] = dfn[Y[i]], xyzzzz[c[cnt++]] = 2;
	}
	sort(c, c + cnt);
	for (int i = cnt - 1; i >= 1; i--) {
	    c[cnt++] = lca(c[i - 1], c[i]);
	}
	sort(c, c + cnt);
	cnt = unique(c, c + cnt) - c;
	res = 1e18;
	pv = 0;
	dfs(1);
	return res;
}

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