Submission #472963

#	Time	Username	Problem	Language	Result	Execution time	Memory
472963		ngpin04	Factories (JOI14_factories)	C++14	15 / 100	8096 ms	144816 KiB

factories

//#include "grader.cpp"
#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int Nmax = 5e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = 3.14159265359;

vector <pair <int, int>> adj[Nmax];

long long d[Nmax];
long long mind[Nmax];

int anc[Nmax][20];
int par[Nmax];
int sz[Nmax];
int h[Nmax];

bool bk[Nmax];

void dfs(int u, int p = -1) {
	anc[u][0] = p;
	for (int i = 1; i < 20; i++) {
		int pr = anc[u][i - 1];
		if (pr < 0) 
			anc[u][i] = -1;
		else 
			anc[u][i] = anc[pr][i - 1];
	}

	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		int w = to.se;
		if (v == p)
			continue;
		h[v] = h[u] + 1;
		d[v] = d[u] + w;
		dfs(v, u);
	}
}

long long dis(int u, int v) {
	if (h[u] < h[v])
		swap(u, v);
	long long res = d[u] + d[v];
	for (int i = 19; i >= 0; i--) 
		if (h[u] - (1 << i) >= h[v])
			u = anc[u][i];
	
	// cerr << u << " " << v << " " << h[u] << " " << h[v] << " " << res << "\n";

	if (u == v)
		return res - (d[v] << 1);

	for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
		u = anc[u][i];
		v = anc[v][i];
	}
	return res - (d[anc[v][0]] << 1);
}

int calc(int u, int p = -1) {
	sz[u] = 1;
	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		if (v == p || bk[v])
			continue;
		sz[u] += calc(v, u);
	} 
	return sz[u];
}

int getcen(int u, int S, int p = -1) {
	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		if (v == p || bk[v] || (sz[v] << 1) <= S)
			continue;
		return getcen(v, S, u);
	}
	return u;
}

int centroid(int u) {
	int r = getcen(u, calc(u));

	bk[r] = true;
	for (pair <int, int> to : adj[r]) {	
		int v = to.fi;
		if (bk[v])
			continue;
		par[centroid(v)] = r;
	}
	return r;
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back(mp(b[i], d[i]));
		adj[b[i]].push_back(mp(a[i], d[i]));
	}
	dfs(0);
	par[centroid(0)] = -1;
	for (int i = 0; i < n; i++)
		mind[i] = ooo;
}

void reset(int u) {
	if (u < 0) 
		return;
	mind[u] = ooo;
	reset(par[u]);
}

void update(int u, int cur) {
	if (cur < 0)
		return;
	// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
	mini(mind[cur], dis(u, cur));
	update(u, par[cur]);
} 

long long getans(int u, int cur) {
	if (cur < 0)
		return ooo;
	// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
	long long res = mind[cur] + dis(u, cur);
	mini(res, getans(u, par[cur]));	
	return res;
}

long long Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		update(x[i], x[i]);

	long long res = ooo;
	for (int i = 0; i < t; i++) 
		mini(res, getans(y[i], y[i]));

	for (int i = 0; i < s; i++)
		reset(x[i]);
	return res;
}

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