Submission #74085

#	Time	Username	Problem	Language	Result	Execution time	Memory
74085		shoemakerjo	Factories (JOI14_factories)	C++14	15 / 100	8025 ms	407780 KiB

factories

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

using namespace std;
#define ll long long
#define pil pair<int, ll>

#define maxn 500010
int n;
vector<vector<pil>> adj(maxn);

//run a centroid decomposition


int subsize[maxn];
bool marked[maxn];
ll dr[19][maxn]; 
ll mycomp[19][maxn]; //which component i am in (specify by centroid is good)
ll curdist[maxn];
int cp[maxn];

ll inf = 1LL << 60;
ll curmin[maxn]; //for the queries
int cl;
int cc;

void dfs(int u, int p, bool op = false) {

	cp[u] = p;
	subsize[u] = 1;
	if (op) {
		// cout << u << " is in " << cc << " at level " << cl << endl;
		dr[cl][u] = curdist[u];
		mycomp[cl][u] = cc;
	}
	for (pil nx : adj[u]) {
		if (nx.first == p || marked[nx.first]) continue;
		curdist[nx.first] = curdist[u] + nx.second;

		dfs(nx.first, u, op);
		subsize[u] += subsize[nx.first];
	}
}

int getcentroid(int u, int csize) {
	curdist[u] = 0LL;
	dfs(u, -1);
	int cur = u;
	bool fin = false;
	while (!fin) {
		fin = true;
		for (pil nx : adj[cur]) {
			if (marked[nx.first] || nx.first == cp[cur]) continue;
			if (subsize[nx.first] > csize/2) {
				fin = false;
				cur = nx.first;
				break;
			}
		}	
	}
	return cur;

}

void go(int u, int csize, int level) {
	int cen = getcentroid(u, csize);
	curdist[cen] = 0LL;
	cc = cen;
	cl = level;
	dfs(cen, -1, true);
	marked[cen] = true;
	for (pil cur : adj[cen]) {
		if (!marked[cur.first])
			go(cur.first, subsize[cur.first], level+1);
	}

}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < 19; i++) {
		fill(mycomp[i], mycomp[i]+maxn, -1);
	}
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].push_back(pil(B[i], D[i]));
		adj[B[i]].push_back(pil(A[i], D[i]));
	}
	fill(curmin, curmin+maxn, inf);
	go(0, n, 0);
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = inf;
	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) continue;
			curmin[mycomp[j][val]] = 
				min(curmin[mycomp[j][val]], dr[j][val]);
		}
	}

	for (int i = 0; i < T; i++) {
		int val = Y[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] != -1) {
				ans = min(ans, 
					curmin[mycomp[j][val]] + dr[j][val]);
			}
		}
	}

	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] != -1)
				curmin[mycomp[j][val]] = inf;
		}
	}

  	return ans;
}

//COULD NOT SUBMIT AT TIME FIRST SOLVED

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