Submission #422537

#	Time	Username	Problem	Language	Result	Execution time	Memory
422537		milleniumEeee	Factories (JOI14_factories)	C++14	33 / 100	8096 ms	160488 KiB

factories

#include "factories.h"
#ifndef EVAL  
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXN = (int)5e5 + 5;
const int MAXQ = (int)1e5 + 5;
const int L = 20;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int get_rand() {
	ll x = rnd();
	x %= (ll)1e9;
	if (x < 0) {
		x = -x;
	}
	return x;
}
int gen(int l, int r) {
	return l + (get_rand() % (r - l + 1));
}

vector <pii> g[MAXN];
int n;
int pr[MAXN][L + 1];
ll d[MAXN];
int tin[MAXN], tout[MAXN], tiktak;
bool used[MAXN];
int sub[MAXN];
vector <int> G[MAXN];
int Gpar[MAXN];
ll opt[MAXN];

void precalc(int v, int par, ll len) {
	tin[v] = ++tiktak;
	pr[v][0] = par;
	d[v] = len;
	for (int lv = 1; lv <= L; lv++) {
		pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
	}
	for (auto [to, dist] : g[v]) {
		if (to == par) {
			continue;
		}
		precalc(to, v, len + dist);
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int get_lca(int a, int b) {
	if (father(a, b)) {
		return a;
	}
	if (father(b, a)) {
		return b;
	}
	for (int lv = L; lv >= 0; lv--) {
		if (!father(pr[a][lv], b)) {
			a = pr[a][lv];
		}
	}
	return pr[a][0];
}

ll get_dist(int a, int b) {
	return d[a] + d[b] - (2ll * d[get_lca(a, b)]);
}


void calc(int v, int par) {
	sub[v] = 1;
	for (auto [to, dist] : g[v]) {
		if (to != par && !used[to]) {
			calc(to, v);
			sub[v] += sub[to];
		}
	}
}

int find_centroid(int v, int par, int sz) {
	for (auto [to, dist] : g[v]) {
		if (to != par && sub[to] > sz / 2 && !used[to]) {
			return find_centroid(to, v, sz);
		}
	}
	return v;
}


void build(int v, int par) {
	calc(v, -1);
	int center = find_centroid(v, -1, sub[v]);
	used[center] = 1;
	if (par != -1) {
		G[center].pb(par);
		G[par].pb(center);
		Gpar[center] = par;
	}
	for (auto [to, dist] : g[center]) {
		if (!used[to]) {
			build(to, center);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	memset(Gpar, -1, sizeof(Gpar));
	fill(opt, opt + MAXN, INF);
	n = N;
	for (int i = 0; i < n - 1; i++) {
		int u = A[i];
		int v = B[i];
		int dist = D[i];
		g[u].pb({v, dist});
		g[v].pb({u, dist});
	}
	precalc(0, 0, 0);
	build(0, -1);
}


void upd(int v, int type) {
	if (type == 1) {
		int cur = v;
		while (1) {
			if (cur == -1) {
				break;
			}
			opt[cur] = min(opt[cur], get_dist(cur, v));
			cur = Gpar[cur];
		}		
	}
	else {
		int cur = v;
		while (1) {
			if (cur == -1) {
				break;
			}
			opt[cur] = INF;
			cur = Gpar[cur];
		}
	}
}

ll get(int v) {
	ll ret = INF;
	int cur = v;
	while (1) {
		if (cur == -1) {
			break;
		}
		ret = min(ret, get_dist(v, cur) + opt[cur]);
		cur = Gpar[cur];
	}
	return ret;
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = INF;
	for (int i = 0; i < S; i++) {
		upd(X[i], 1);
	}
	for (int i = 0; i < T; i++) {
		ans = min(ans, get(Y[i]));
	}
	for (int i = 0; i < S; i++) {
		upd(X[i], -1);
	}
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void precalc(int, int, long long int)':
factories.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'void calc(int, int)':
factories.cpp:89:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:98:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:116:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |  for (auto [to, dist] : g[center]) {
      |            ^

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