Submission #302427

#	Time	Username	Problem	Language	Result	Execution time	Memory
302427		hexan	Factories (JOI14_factories)	C++14	0 / 100	27 ms	24192 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];
vector<int> nxt[N];
int dist[N];
int p[N], w[N];
int root = -1;

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;
		dist[to.x] = dist[v] + to.y;
		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) {
	for(auto to : g[v]) {
		if (p[to.x] == -1) {
			int nx = -1;
			dist[to.x] = to.y;
			dfs(to.x, -1, nx, n / 2);
			nxt[v].push_back(nx);
			w[nx] = dist[nx];
			p[nx] = v;
			dec(nx, n / 2);
		}
	}
}

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

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		//--A[i]; --B[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);
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < n; j++) {
			f[i][j] = INF;
		}
	}
}


int timer = 0;

ll ans;

void calc(int v) {
	vector<ll> fu = {f[0][v], f[1][v]};
	chkmin(ans, fu[0] + fu[1]);
	for(int to : nxt[v]) {
		for(int x : {0, 1}) {
			if (timer != used[x][to]) {
				used[x][to] = timer;
				cnt[x][to] = 0;
				f[x][to] = INF;
			}
		}
		chkmin(ans, fu[0] + f[1][to] + w[to]);
		chkmin(ans, fu[1] + f[0][to] + w[to]);
		chkmin(fu[0], f[0][to] + w[to]);
		chkmin(fu[1], f[1][to] + w[to]);
		if (cnt[0][to] && cnt[1][to]) {
			calc(to);
		}
	}
}

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 W = 0;
			while (1) {
				if (used[i][x] != timer) {
					used[i][x] = timer;
					f[i][x] = INF;
					cnt[i][x] = 0;
				}
				f[i][x] = min(f[i][x], W);
				cnt[i][x] = 1;
				if (p[x] != x) {
					W += w[x];
					x = p[x];
				} else {
					break;
				}
			}
		}
	}
	calc(root);
	return ans;
}

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