oj.uz

Submission #422552

# Submission time Handle Problem Language Result Execution time Memory
422552 2021-06-10T08:27:36 Z milleniumEeee Factories (JOI14_factories) C++11
33 / 100
 8000 ms 157020 KB 
#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;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30028 KB Output is correct
2 Correct 687 ms 38504 KB Output is correct
3 Correct 1330 ms 38520 KB Output is correct
4 Correct 1303 ms 38772 KB Output is correct
5 Correct 686 ms 38972 KB Output is correct
6 Correct 288 ms 38604 KB Output is correct
7 Correct 1337 ms 38812 KB Output is correct
8 Correct 1372 ms 38684 KB Output is correct
9 Correct 683 ms 38940 KB Output is correct
10 Correct 301 ms 38700 KB Output is correct
11 Correct 1306 ms 38652 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29888 KB Output is correct
2 Correct 2845 ms 126896 KB Output is correct
3 Correct 6127 ms 128740 KB Output is correct
4 Correct 1024 ms 128876 KB Output is correct
5 Correct 4244 ms 157020 KB Output is correct
6 Correct 6059 ms 129936 KB Output is correct
7 Correct 3722 ms 57448 KB Output is correct
8 Correct 501 ms 58400 KB Output is correct
9 Correct 1684 ms 61692 KB Output is correct
10 Correct 3597 ms 58796 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30028 KB Output is correct
2 Correct 687 ms 38504 KB Output is correct
3 Correct 1330 ms 38520 KB Output is correct
4 Correct 1303 ms 38772 KB Output is correct
5 Correct 686 ms 38972 KB Output is correct
6 Correct 288 ms 38604 KB Output is correct
7 Correct 1337 ms 38812 KB Output is correct
8 Correct 1372 ms 38684 KB Output is correct
9 Correct 683 ms 38940 KB Output is correct
10 Correct 301 ms 38700 KB Output is correct
11 Correct 1306 ms 38652 KB Output is correct
12 Correct 19 ms 29888 KB Output is correct
13 Correct 2845 ms 126896 KB Output is correct
14 Correct 6127 ms 128740 KB Output is correct
15 Correct 1024 ms 128876 KB Output is correct
16 Correct 4244 ms 157020 KB Output is correct
17 Correct 6059 ms 129936 KB Output is correct
18 Correct 3722 ms 57448 KB Output is correct
19 Correct 501 ms 58400 KB Output is correct
20 Correct 1684 ms 61692 KB Output is correct
21 Correct 3597 ms 58796 KB Output is correct
22 Correct 3763 ms 128448 KB Output is correct
23 Correct 3881 ms 130852 KB Output is correct
24 Execution timed out 8080 ms 130452 KB Time limit exceeded
25 Halted 0 ms 0 KB -