Submission #656573

#	Time	Username	Problem	Language	Result	Execution time	Memory
656573		SanguineChameleon	Factories (JOI14_factories)	C++14	100 / 100	3427 ms	170700 KiB

factories

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

const long long inf = (long long)1e18 + 20;
const int ms = 5e5 + 20;
const int st = 22;
vector<pair<int, int>> adj[ms];
long long dt[ms][st];
long long mi[ms];
int de[ms];
int par[ms];
bool f[ms];
int sz[ms];

void dfs1(int u, int pr) {
	sz[u] = 1;
	for (auto x: adj[u]) {
		int v = x.first;
		if (v != pr && !f[v]) {
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}
}

int ctr(int r, int u, int pr) {
	for (auto x: adj[u]) {
		int v = x.first;
		if (v != pr && !f[v]) {
			if (sz[v] * 2 > sz[r]) {
				return ctr(r, v, u);
			}
		}
	}
	return u;
}

void dfs2(int u, int pr, int d) {
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != pr && !f[v]) {
			dt[v][d] = dt[u][d] + w;
			dfs2(v, u, d);
		}
	}
}

void build(int u, int pr, int d) {
	dfs1(u, -1);
	int v = ctr(u, u, -1);
	f[v] = true;
	de[v] = d;
	par[v] = pr;
	dt[v][d] = 0;
	dfs2(v, -1, d);
	for (auto x: adj[v]) {
		int w = x.first;
		if (!f[w]) {
			build(w, v, d + 1);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 1; i <= N; i++) {
		mi[i] = inf;
	}
	for (int i = 0; i < N - 1; i++) {
		int u = A[i] + 1;
		int v = B[i] + 1;
		int w = D[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	build(1, -1, 1);
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		int u = X[i] + 1;
		int d = de[u];
		int cc = u;
		while (d >= 1) {
			mi[cc] = min(mi[cc], dt[u][d]);
			cc = par[cc];
			d--;
		}
	}
	long long res = inf;
	for (int i = 0; i < T; i++) {
		int u = Y[i] + 1;
		int d = de[u];
		int cc = u;
		while (d >= 1) {
			res = min(res, mi[cc] + dt[u][d]);
			cc = par[cc];
			d--;
		}
	}
	for (int i = 0; i < S; i++) {
		int u = X[i] + 1;
		int d = de[u];
		int cc = u;
		while (d >= 1) {
			mi[cc] = inf;
			cc = par[cc];
			d--;
		}
	}
	return res;
}

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