Submission #74285

#	Time	Username	Problem	Language	Result	Execution time	Memory
74285		kingpig9	Factories (JOI14_factories)	C++11	0 / 100	35 ms	25080 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

const int MAXN = 5e5 + 10;
const int MAXLG = 19;
const ll INF = 1e16;

void setmin (ll &a, ll b) {
	if (a > b) {
		a = b;
	}
}

int N;
vector<pll> adj[MAXN];
ll ans[MAXN];
int sz[MAXN];
bool vis[MAXN];

int dfssz (int x, int p) {
	sz[x] = 1;
	for (auto py : adj[x]) {
		int y = py.fi;
		if (y != p && !vis[y]) {
			sz[x] += dfssz(y, x);
		}
	}
	return sz[x];
}

int findcent (int x, int p, int s) {
	for (auto py : adj[x]) {
		int y = py.fi;
		if (y != p && !vis[y]) {
			return findcent(y, x, s);
		}
	}
	return x;
}

int par[MAXN];
int hcent[MAXN];
ll dist[20][MAXN];

//Note: here, you are not actually dfsing through centroid tree - you are dfsing through the original tree.
void dfslow (int x, int p, int h, ll w) {
	dist[h][x] = w;

	for (pll py : adj[x]) {
		int y = py.fi;
		if (y != p && !vis[y]) {
			dfslow(y, x, h, w + py.se);
		}
	}
}

void dfsc (int x, int pc) {
	int szcmp = dfssz(x, -1);
	x = findcent(x, -1, szcmp);
	vis[x] = true;
	par[x] = pc;
	if (pc != -1) {
		hcent[x] = hcent[pc] + 1;
	}
	dfslow(x, -1, hcent[x], 0ll);	//dfs to unvisited vertices - or "low" vertices (in the subtree).
	for (auto py : adj[x]) {
		int y = py.fi;
		if (y != pc && !vis[y]) {
			dfsc(y, x);
		}
	}
}

void update (int x, bool reset) {
	for (int i = x; i != -1; i = par[i]) {
		if (reset) {
			ans[i] = INF;
		} else {
			setmin(ans[i], dist[hcent[i]][x]);
		}
	}
}

ll query (int x) {
	ll res = INF;
	for (int i = x; i != -1; i = par[i]) {
		setmin(res, ans[i] + dist[hcent[i]][x]);
	}
	return res;
}

void Init (int nn, int a[], int b[], int d[]) {
	N = nn;
	for (int i = 0; i < N - 1; i++) {
		adj[a[i]].push_back(pll(b[i], d[i]));
		adj[b[i]].push_back(pll(a[i], d[i]));
	}

	for (int i = 0; i < N; i++) {
		ans[i] = INF;
	}
	dfsc(0, -1);
	exit(0);
}

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

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