oj.uz

Submission #422644

# Submission time Handle Problem Language Result Execution time Memory
422644 2021-06-10T09:31:44 Z milleniumEeee Factories (JOI14_factories) C++17
15 / 100
 763 ms 143872 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];
pii arr[MAXN];
int ind = 1;
pii bound[MAXN];

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 30176 KB Output is correct
2 Correct 454 ms 39820 KB Output is correct
3 Correct 542 ms 39856 KB Output is correct
4 Correct 763 ms 39844 KB Output is correct
5 Correct 636 ms 40072 KB Output is correct
6 Correct 302 ms 39928 KB Output is correct
7 Correct 645 ms 39852 KB Output is correct
8 Correct 557 ms 39904 KB Output is correct
9 Correct 566 ms 39948 KB Output is correct
10 Correct 301 ms 39876 KB Output is correct
11 Correct 575 ms 39900 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30024 KB Output is correct
2 Runtime error 758 ms 143872 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30176 KB Output is correct
2 Correct 454 ms 39820 KB Output is correct
3 Correct 542 ms 39856 KB Output is correct
4 Correct 763 ms 39844 KB Output is correct
5 Correct 636 ms 40072 KB Output is correct
6 Correct 302 ms 39928 KB Output is correct
7 Correct 645 ms 39852 KB Output is correct
8 Correct 557 ms 39904 KB Output is correct
9 Correct 566 ms 39948 KB Output is correct
10 Correct 301 ms 39876 KB Output is correct
11 Correct 575 ms 39900 KB Output is correct
12 Correct 21 ms 30024 KB Output is correct
13 Runtime error 758 ms 143872 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -