oj.uz

Submission #422645

# Submission time Handle Problem Language Result Execution time Memory
422645 2021-06-10T09:32:49 Z milleniumEeee Factories (JOI14_factories) C++17
100 / 100
 6441 ms 294024 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
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(b<a)a=b;}
 
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;
bool used[MAXN];
int sub[MAXN];
vector <int> G[MAXN];
int Gpar[MAXN];
ll opt[MAXN];
ll d[MAXN];

int ind = 1;
pii arr[MAXN * 2];
pii bound[MAXN * 2];
pii tb[MAXN * 2][L + 1];
int lg[MAXN * 2];
pii merge(pii a, pii b) {
	if (a.sc < b.sc) {
		return a;
	} else {
		return b;
	}
}
void build_table(int n) {
	lg[1] = 0;
	for (int i = 2; i <= n; i++) {
		lg[i] = lg[i >> 1] + 1;
	}
	for (int pw = 0; pw <= L; pw++) {
		for (int i = 1; i <= n; i++) {
			if (pw == 0) {
				tb[i][pw] = arr[i];
			}
			else if (i + (1 << pw) - 1 <= n) {
				tb[i][pw] = merge(tb[i][pw - 1], tb[i + (1 << (pw - 1))][pw - 1]);
			}
		}
	}
}
int get_lca(int a, int b) {
	int l = min(bound[a].fr, bound[b].fr);
	int r = max(bound[a].sc, bound[b].sc);
	int sz = lg[r - l + 1];
	pii lca = merge(tb[l][sz], tb[r - (1 << sz) + 1][sz]);
	return lca.fr;
}

void precalc(int v, int par, int dep = 0, ll len = 0) {
	arr[ind++] = {v, dep};
	d[v] = len;
	for (auto [to, dist] : g[v]) {
		if (to != par) {
			precalc(to, v, dep + 1, len + dist);
			arr[ind++] = {v, dep};
		}
	}
}

ll get_dist(int a, int b) {
	int lca = get_lca(a, b);
	return d[a] + d[b] - (d[lca] << 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, -1);
	for (int i = 0; i < n; i++) {
		bound[i] = {1e9, -1e9};
	}
	for (int i = 1; i < ind; i++) {
		int v = arr[i].fr;
		chmin(bound[v].fr, i);
		chmax(bound[v].sc, i);
	}
	build_table(ind - 1);
	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 29 ms 30156 KB Output is correct
2 Correct 485 ms 39840 KB Output is correct
3 Correct 575 ms 39900 KB Output is correct
4 Correct 637 ms 39864 KB Output is correct
5 Correct 574 ms 40000 KB Output is correct
6 Correct 302 ms 39852 KB Output is correct
7 Correct 575 ms 39880 KB Output is correct
8 Correct 595 ms 39836 KB Output is correct
9 Correct 622 ms 39960 KB Output is correct
10 Correct 343 ms 39852 KB Output is correct
11 Correct 549 ms 39840 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30028 KB Output is correct
2 Correct 2790 ms 256004 KB Output is correct
3 Correct 3917 ms 255568 KB Output is correct
4 Correct 1580 ms 258000 KB Output is correct
5 Correct 5203 ms 268952 KB Output is correct
6 Correct 4290 ms 257076 KB Output is correct
7 Correct 1983 ms 82864 KB Output is correct
8 Correct 659 ms 84320 KB Output is correct
9 Correct 1960 ms 85548 KB Output is correct
10 Correct 1951 ms 84216 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30156 KB Output is correct
2 Correct 485 ms 39840 KB Output is correct
3 Correct 575 ms 39900 KB Output is correct
4 Correct 637 ms 39864 KB Output is correct
5 Correct 574 ms 40000 KB Output is correct
6 Correct 302 ms 39852 KB Output is correct
7 Correct 575 ms 39880 KB Output is correct
8 Correct 595 ms 39836 KB Output is correct
9 Correct 622 ms 39960 KB Output is correct
10 Correct 343 ms 39852 KB Output is correct
11 Correct 549 ms 39840 KB Output is correct
12 Correct 21 ms 30028 KB Output is correct
13 Correct 2790 ms 256004 KB Output is correct
14 Correct 3917 ms 255568 KB Output is correct
15 Correct 1580 ms 258000 KB Output is correct
16 Correct 5203 ms 268952 KB Output is correct
17 Correct 4290 ms 257076 KB Output is correct
18 Correct 1983 ms 82864 KB Output is correct
19 Correct 659 ms 84320 KB Output is correct
20 Correct 1960 ms 85548 KB Output is correct
21 Correct 1951 ms 84216 KB Output is correct
22 Correct 4083 ms 257584 KB Output is correct
23 Correct 4040 ms 259864 KB Output is correct
24 Correct 5922 ms 258060 KB Output is correct
25 Correct 5872 ms 261280 KB Output is correct
26 Correct 5995 ms 257864 KB Output is correct
27 Correct 6441 ms 294024 KB Output is correct
28 Correct 1716 ms 286760 KB Output is correct
29 Correct 5959 ms 281868 KB Output is correct
30 Correct 5650 ms 281660 KB Output is correct
31 Correct 5627 ms 282052 KB Output is correct
32 Correct 2058 ms 93168 KB Output is correct
33 Correct 698 ms 91840 KB Output is correct
34 Correct 1580 ms 88408 KB Output is correct
35 Correct 1557 ms 88416 KB Output is correct
36 Correct 2213 ms 88552 KB Output is correct
37 Correct 2133 ms 88556 KB Output is correct