Submission #472967

#	Time	Username	Problem	Language	Result	Execution time	Memory
472967		ngpin04	Factories (JOI14_factories)	C++14	15 / 100	1217 ms	187608 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 t[Nmax][20];
int tin[Nmax];
int par[Nmax];
int sz[Nmax];
int h[Nmax];
int timer;

bool bk[Nmax];

int getmin(int u, int v) {
	return (h[u] < h[v]) ? u : v;
}

void dfs(int u, int p = -1) {
	t[++timer][0] = u;
	tin[u] = timer;
	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);
		t[++timer][0] = u;
	}
}

void build() {
	for (int j = 1; j < 20; j++)
	for (int i = 1; i + (1 << j) - 1 <= timer; i++)
		t[i][j] = getmin(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
}

long long dis(int u, int v) {
	int l = tin[u];
	int r = tin[v];
	if (l > r)
		swap(l, r);
	int lg = log2(r - l + 1);
	int p = getmin(t[l][lg], t[r - (1 << lg) + 1][lg]);
	// cerr << u << " " << v << " " << p << "\n";
	return d[u] + d[v] - (d[p] << 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);
	build();
	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