Submission #306340

#	Time	Username	Problem	Language	Result	Execution time	Memory
306340		syy	Factories (JOI14_factories)	C++17	100 / 100	4392 ms	163756 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define f first
#define s second

vector <pi> adjlist[500005];
int sub[500005], lvl[500005], p[500005];
ll dist[500005][19], ans[500005];
stack <int> st;
ll INF = 1e18;

int subtrsz(int x, int par, int l) {
	sub[x] = 1;
	//subtree size is 1
	for (auto it:adjlist[x]) {
		if (lvl[it.f] != -1) continue;
		// already added to centroid tree
		if (it.f == par) continue;
		if (l) dist[it.f][l-1] = dist[x][l-1] + it.s;
		sub[x] += subtrsz(it.f, x, l);
	}
	return sub[x];
}

int findcent(int x, int par, int n) {
	//n is size of subtree
	for (auto it:adjlist[x]) {
		if (lvl[it.f] != -1) continue;
		// Already added to centroid tree
		if (it.f != par and sub[it.f] > n/2) {
			return findcent(it.f, x, n);
		}
	}
	return x; // No subtree has size > n/2
	// so you are the centroid
}
//building from node x, with parent par, level l
void build(int x, int par, int l) {
	int n = subtrsz(x, par, l);
	int cent = findcent(x, par, n);
	// find centroid with the subtree size
	if (par == -1) par = cent; //par of root is itself
	p[cent] = par; //set parent of centroid
	// to be the previous centroid
	lvl[cent] = l;
	for (auto it:adjlist[cent]) {
		if (lvl[it.f] != -1) continue;
		// already added to centroid tree
		dist[it.f][l] = it.s; 
		// distance from this node to the centroid at level l
		build(it.f, cent, l+1);
	}
}

void update(int x) {
	int l = lvl[x];
	int y = x;
	while (l != -1) {
		ans[y] = min(ans[y], dist[x][l]);
		//ans[y] = min distance from any node
		//of Factory A to y.
		//here we process by x
		st.push(y);
		y = p[y];
		l--;
	}
}

ll findans(int x) {
	ll ret = INF;
	int l = lvl[x];
	int y = x;
	while (l != -1) {
		ret = min(ret, ans[y] + dist[x][l]);
		//for every centroid, add dist from
		//best Factory A node to querying Factory B node
		//then min with running answer
		y = p[y];
		l--;
	}
	return ret;
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N-1; i++) {
		adjlist[A[i]].push_back(pi(B[i], D[i]));
		adjlist[B[i]].push_back(pi(A[i], D[i]));
	}
	memset(lvl, -1, sizeof lvl);
	build(0, -1, 0); //build centroid tree
	for (int i = 0; i < N; i++) ans[i] = INF;
	//for (int i=0;i<N;++i)cout<<p[i]<<' '<<lvl[i]<<' '<<dist[i][0]<<'\n';cout<<'\n';
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) update(X[i]);
	//find min dist from every node to Factory A nodes
	ll ret = INF;
	for (int i = 0; i < T; i++) ret = min(ret, findans(Y[i]));
	//find min dist from every node to Factory B nodes
	while (st.size()) {
		ans[st.top()] = INF;
		st.pop();
	}
	return ret;
}

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