Submission #111130

#	Time	Username	Problem	Language	Result	Execution time	Memory
111130		Plasmatic	Factories (JOI14_factories)	C++11	100 / 100	6956 ms	218696 KiB

factories

//============================================================================
// Name        : joi14p1.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

using namespace std;

typedef long long ll;

// Scan and Debug
void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F f, R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)

const int MAX = 500001;

struct ed {
	int v, w;
};

vector<ed> matrix[MAX];
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N,
	sz[MAX], par[MAX], lv[MAX];
bool blocked[MAX];
ll bestFor[MAX];
vector<ll> dis[MAX];

int gsz(int cur, int par) {
	sz[cur] = 1;
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v])
			sz[cur] += gsz(adj.v, cur);
	return sz[cur];
}

int gcentroid(int cur, int par, int half) {
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v] && sz[adj.v] > half)
			return gcentroid(adj.v, cur, half);
	return cur;
}

void dfs(int cur, int par=-1, ll __dis=0) {
	dis[cur].push_back(__dis);
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v])
			dfs(adj.v, cur, __dis + adj.w);
}

int nxt[MAX], tpar[MAX], nxtPtr = -1;
ll tdis[MAX];

int decomp(int cur=0, int __par=-1, int __lv=0) {
	gsz(cur, __par);
	if (sz[cur] == 1) {// If size is one, centroid is self
		lv[cur] = __lv;
		return cur;
	}

	int centroid = gcentroid(cur, __par, sz[cur] >> 1);
	lv[centroid] = __lv;
	blocked[centroid] = true;

	dis[centroid].push_back(0);
	tpar[centroid] = -1;
	tdis[centroid] = 0;
	nxt[++nxtPtr] = centroid;
	while (nxtPtr >= 0) {
		int cur = nxt[nxtPtr]; nxtPtr--;
		for (ed adj : matrix[cur]) {
			if ((adj.v ^ tpar[cur]) && !blocked[adj.v]) {
				nxt[++nxtPtr] = adj.v;
				tpar[adj.v] = cur;
				tdis[adj.v] = tdis[cur] + adj.w;
				dis[adj.v].push_back(tdis[adj.v]);
			}
		}
	}

	for (ed adj : matrix[centroid])
		if (!blocked[adj.v])
			par[decomp(adj.v, centroid, __lv + 1)] = centroid;

	return centroid;
}

// Grader Functions
void Init(int N_, int A[], int B[], int D[]) {
	N = N_;
	for (int i = 0; i < N - 1; i++) {
		matrix[A[i]].push_back({B[i], D[i]});
		matrix[B[i]].push_back({A[i], D[i]});
	}

	// Init Centroid Tree
	par[decomp()] = -1;
	memset(bestFor, 0x3f, sizeof bestFor);
}

int back[20000001], backSz = 0;

long long Query(int S, int X[], int T, int Y[]) {
	ll best = INF;
	backSz = 0;

	for (int i = 0; i < T; i++) {
		for (int cur = Y[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--) {
			bestFor[cur] = min(bestFor[cur], dis[Y[i]][clv]), assert(cur != par[cur]);
			back[backSz++] = cur;
		}
	}

	for (int i = 0; i < S; i++)
		for (int cur = X[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--)
			best = min(best, dis[X[i]][clv] + bestFor[cur]), assert(cur != par[cur]);

	for (int i = 0; i < backSz; i++)
		bestFor[back[i]] = INF;

	return best;
}

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