Submission #302721

#	Time	Username	Problem	Language	Result	Execution time	Memory
302721		hexan	Factories (JOI14_factories)	C++14	100 / 100	6381 ms	166584 KiB

factories

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

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = 5e5 + 1;
const int lg = 20;
vector<pair<int, int>> g[N];
int p[N];
ll d[lg][N], dth[N];
int root = -1;


void tata(int v, int pa, ll cu, int death) {
	d[death][v] = cu;
	for(auto to : g[v]) {
		if (to.x == pa || p[to.x] != -1) continue;
		tata(to.x, v, cu + to.y, death);
	}
}

int dfs(int v, int pa, int &c, int n) {
	int sz = 1;
	for(auto to : g[v]) {
		if (to.x == pa || p[to.x] != -1) continue;
		sz += dfs(to.x, v, c, n);
	}
	if (c == -1 && (sz * 2 >=  n || pa == -1))
		c = v;
	return sz;
}

void dec(int v, int n) {
	tata(v, -1, 0, dth[v]);
	for(auto to : g[v]) {
		if (p[to.x] == -1) {
			int nx = -1;
			dfs(to.x, -1, nx, n / 2);
			p[nx] = v;
			dth[nx] = dth[v] + 1;
			dec(nx, n / 2);
		}
	}
}

int n;
const ll INF = 1e18;
ll used[N], f[2][N];

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	fill(p, p + N, -1);
	dfs(0, -1, root, n);
	p[root] = root;
	dec(root, N);
}


int timer = 0;

ll ans;

long long Query(int S, int X[], int T, int Y[]) {
	timer++;	
	ans = INF;
	for(int i : {0, 1}) {
		for(int j = 0; j < (i == 0 ? S : T); j++) {
			int x;
			if (!i) x = X[j];
			else x = Y[j];
			ll val = x, e = dth[x];
			while (1) {
				if (used[x] != timer) {
					used[x] = timer;
					f[0][x] = INF;
					f[1][x] = INF;
				}
				f[i][x] = min(f[i][x], d[e][val]);
				chkmin(ans, f[0][x] + f[1][x]);
				if (p[x] != x) {
					x = p[x];
					--e;
				} else {
					break;
				}
			}
		}
	}	
	return ans;
}

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