제출 #302445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302445		hexan	공장들 (JOI14_factories)	C++14	0 / 100	36 ms	24184 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];
ll w[N];
int root = -1;

void kek(int x, int p) {
	for(auto to : g[x]) {
		if (to.x == p) continue;
		w[to.x] = w[x] + to.y;
		kek(to.x, x);
	}
}

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


int timer = 0;

ll ans;

void calc(int v) {
	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(f[0][v], f[0][to]);
		chkmin(f[1][v], f[1][to]);
		if (cnt[0][to] && cnt[1][to]) {
			calc(to);
		}
	}
	chkmin(ans, f[0][v] + f[1][v] - 2 * w[v]);
}

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 = w[x];
			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], val);
				cnt[i][x] = 1;
				if (p[x] != x) {
					x = p[x];
				} else {
					break;
				}
			}
		}
	}	calc(root);
	return ans;
}

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