Submission #160504

#	Time	Username	Problem	Language	Result	Execution time	Memory
160504		iefnah06	Factories (JOI14_factories)	C++11	100 / 100	7477 ms	185244 KiB

factories

#include "factories.h"

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

using ll = long long;
const ll INF = 1e18;

const int MAXN = 5.1e5;
struct edge_t {
	int c[2];
	ll w;
	int other(int a) {
		assert(a == c[0] || a == c[1]);
		return c[0] ^ c[1] ^ a;
	}
} E[MAXN];
vector<int> adj[MAXN];

bool isDead[MAXN];
int par[MAXN];
ll dists[MAXN][20];
int ptrs[MAXN];

int dfsSz(int cur, int prv) {
	if (isDead[cur]) return 0;
	int ans = 1;
	for (int e : adj[cur]) {
		int nxt = E[e].other(cur);
		if (nxt == prv) continue;
		ans += dfsSz(nxt, cur);
	}
	return ans;
}

int getCentroid(int cur, int prv, int sz) {
	if (isDead[cur]) return -1;
	int curSz = 1;
	for (int e : adj[cur]) {
		int nxt = E[e].other(cur);
		if (nxt == prv) continue;
		int ch = getCentroid(nxt, cur, sz);
		if (ch >= 0) {
			return ch;
		} else {
			curSz += -1-ch;
		}
	}

	if (curSz * 2 >= sz) {
		return cur;
	} else {
		return -1-curSz;
	}
}

void genDists(int cur, int centroid, int prv, ll dist) {
	if (isDead[cur]) return;
	if (cur != centroid) {
		par[cur] = centroid;
	}
	dists[cur][ptrs[cur]++] = dist;
	for (int e : adj[cur]) {
		int nxt = E[e].other(cur);
		if (nxt == prv) continue;
		genDists(nxt, centroid, cur, dist + E[e].w);
	}
}

void buildCentroid(int cur) {
	int sz = dfsSz(cur, -1);
	cur = getCentroid(cur, -1, sz);
	genDists(cur, cur, -1, 0);
	isDead[cur] = true;

	for (int e : adj[cur]) {
		int nxt = E[e].other(cur);
		if (isDead[nxt]) continue;
		buildCentroid(nxt);
	}
}

ll minDist[MAXN];

void Init(int N, int A[], int B[], int D[]) {
	for (int e = 0; e < N-1; e++) {
		E[e] = {A[e], B[e], D[e]};
		adj[A[e]].push_back(e);
		adj[B[e]].push_back(e);
	}

	for (int i = 0; i < N; i++) {
		par[i] = -1;
	}
	buildCentroid(0);
	for (int i = 0; i < N; i++) {
		minDist[i] = INF;
	}
}


void update(int v, bool add = true) {
	for (int cur = v, i = ptrs[cur]-1; cur != -1; cur = par[cur], i--) {
		assert(i >= 0);
		if (add) {
			minDist[cur] = min(minDist[cur], dists[v][i]);
		} else {
			minDist[cur] = INF;
		}
	}
}

ll query(int v) {
	ll ans = INF;
	for (int cur = v, i = ptrs[cur]-1; cur != -1; cur = par[cur], i--) {
		assert(i >= 0);
		ans = min(ans, minDist[cur] + dists[v][i]);
	}
	return ans;
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		update(X[i]);
	}
	ll ans = INF;
	for (int i = 0; i < T; i++) {
		ans = min(ans, query(Y[i]));
	}
	for (int i = 0; i < S; i++) {
		update(X[i], false);
	}
	return ans;
}

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