oj.uz

Submission #422557

# Submission time Handle Problem Language Result Execution time Memory
422557 2021-06-10T08:32:48 Z milleniumEeee Factories (JOI14_factories) C++17
33 / 100
 8000 ms 150352 KB 
#pragma GCC optimize("Ofast")
#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 = 19;
 
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] - (d[get_lca(a, b)] << 1);
}
 
 
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 >> 1) && !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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30028 KB Output is correct
2 Correct 665 ms 38516 KB Output is correct
3 Correct 1320 ms 38652 KB Output is correct
4 Correct 1298 ms 38648 KB Output is correct
5 Correct 677 ms 38740 KB Output is correct
6 Correct 265 ms 38568 KB Output is correct
7 Correct 1324 ms 38600 KB Output is correct
8 Correct 1367 ms 38724 KB Output is correct
9 Correct 691 ms 38840 KB Output is correct
10 Correct 263 ms 38600 KB Output is correct
11 Correct 1317 ms 38656 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29772 KB Output is correct
2 Correct 2625 ms 126872 KB Output is correct
3 Correct 5573 ms 128016 KB Output is correct
4 Correct 903 ms 128944 KB Output is correct
5 Correct 4511 ms 150352 KB Output is correct
6 Correct 6465 ms 129260 KB Output is correct
7 Correct 3922 ms 57384 KB Output is correct
8 Correct 450 ms 58440 KB Output is correct
9 Correct 1644 ms 60800 KB Output is correct
10 Correct 4083 ms 58656 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30028 KB Output is correct
2 Correct 665 ms 38516 KB Output is correct
3 Correct 1320 ms 38652 KB Output is correct
4 Correct 1298 ms 38648 KB Output is correct
5 Correct 677 ms 38740 KB Output is correct
6 Correct 265 ms 38568 KB Output is correct
7 Correct 1324 ms 38600 KB Output is correct
8 Correct 1367 ms 38724 KB Output is correct
9 Correct 691 ms 38840 KB Output is correct
10 Correct 263 ms 38600 KB Output is correct
11 Correct 1317 ms 38656 KB Output is correct
12 Correct 19 ms 29772 KB Output is correct
13 Correct 2625 ms 126872 KB Output is correct
14 Correct 5573 ms 128016 KB Output is correct
15 Correct 903 ms 128944 KB Output is correct
16 Correct 4511 ms 150352 KB Output is correct
17 Correct 6465 ms 129260 KB Output is correct
18 Correct 3922 ms 57384 KB Output is correct
19 Correct 450 ms 58440 KB Output is correct
20 Correct 1644 ms 60800 KB Output is correct
21 Correct 4083 ms 58656 KB Output is correct
22 Correct 3735 ms 128392 KB Output is correct
23 Correct 4059 ms 130908 KB Output is correct
24 Execution timed out 8042 ms 129792 KB Time limit exceeded
25 Halted 0 ms 0 KB -