oj.uz

Submission #422639

# Submission time Handle Problem Language Result Execution time Memory
422639 2021-06-10T09:30:04 Z milleniumEeee Factories (JOI14_factories) C++17
15 / 100
 1042 ms 461400 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];

struct Sparse_Table {
	pii tb[MAXN * 2][L + 1];
	int lg[MAXN * 2];
	Sparse_Table () {
		
	}
	pii merge(pii a, pii b) {
		if (a.sc < b.sc) {
			return a;
		} else {
			return b;
		}
	}
	void build(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;
	}
}Tree;

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 = Tree.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);
	}
	Tree.build(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 113 ms 186556 KB Output is correct
2 Correct 550 ms 194792 KB Output is correct
3 Correct 722 ms 194872 KB Output is correct
4 Correct 637 ms 194804 KB Output is correct
5 Correct 680 ms 195008 KB Output is correct
6 Correct 377 ms 194816 KB Output is correct
7 Correct 636 ms 194936 KB Output is correct
8 Correct 661 ms 194980 KB Output is correct
9 Correct 668 ms 195012 KB Output is correct
10 Correct 381 ms 194860 KB Output is correct
11 Correct 630 ms 194884 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 186324 KB Output is correct
2 Runtime error 1042 ms 461400 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 113 ms 186556 KB Output is correct
2 Correct 550 ms 194792 KB Output is correct
3 Correct 722 ms 194872 KB Output is correct
4 Correct 637 ms 194804 KB Output is correct
5 Correct 680 ms 195008 KB Output is correct
6 Correct 377 ms 194816 KB Output is correct
7 Correct 636 ms 194936 KB Output is correct
8 Correct 661 ms 194980 KB Output is correct
9 Correct 668 ms 195012 KB Output is correct
10 Correct 381 ms 194860 KB Output is correct
11 Correct 630 ms 194884 KB Output is correct
12 Correct 103 ms 186324 KB Output is correct
13 Runtime error 1042 ms 461400 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -