oj.uz

Submission #422537

# Submission time Handle Problem Language Result Execution time Memory
422537 2021-06-10T08:10:51 Z milleniumEeee Factories (JOI14_factories) C++14
33 / 100
 8000 ms 160488 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 = 20;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int get_rand() {
	ll x = rnd();
	x %= (ll)1e9;
	if (x < 0) {
		x = -x;
	}
	return x;
}
int gen(int l, int r) {
	return l + (get_rand() % (r - l + 1));
}

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] - (2ll * d[get_lca(a, b)]);
}


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 / 2 && !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:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'void calc(int, int)':
factories.cpp:89:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:98:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:116:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |  for (auto [to, dist] : g[center]) {
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30260 KB Output is correct
2 Correct 735 ms 44268 KB Output is correct
3 Correct 1460 ms 46724 KB Output is correct
4 Correct 1451 ms 46864 KB Output is correct
5 Correct 756 ms 47140 KB Output is correct
6 Correct 357 ms 47000 KB Output is correct
7 Correct 1443 ms 47120 KB Output is correct
8 Correct 1475 ms 47168 KB Output is correct
9 Correct 727 ms 47448 KB Output is correct
10 Correct 284 ms 47172 KB Output is correct
11 Correct 1411 ms 47128 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29900 KB Output is correct
2 Correct 2877 ms 129544 KB Output is correct
3 Correct 6112 ms 132200 KB Output is correct
4 Correct 1025 ms 132188 KB Output is correct
5 Correct 4208 ms 160488 KB Output is correct
6 Correct 6760 ms 133420 KB Output is correct
7 Correct 4349 ms 65040 KB Output is correct
8 Correct 476 ms 66144 KB Output is correct
9 Correct 1755 ms 69304 KB Output is correct
10 Correct 4271 ms 66248 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30260 KB Output is correct
2 Correct 735 ms 44268 KB Output is correct
3 Correct 1460 ms 46724 KB Output is correct
4 Correct 1451 ms 46864 KB Output is correct
5 Correct 756 ms 47140 KB Output is correct
6 Correct 357 ms 47000 KB Output is correct
7 Correct 1443 ms 47120 KB Output is correct
8 Correct 1475 ms 47168 KB Output is correct
9 Correct 727 ms 47448 KB Output is correct
10 Correct 284 ms 47172 KB Output is correct
11 Correct 1411 ms 47128 KB Output is correct
12 Correct 20 ms 29900 KB Output is correct
13 Correct 2877 ms 129544 KB Output is correct
14 Correct 6112 ms 132200 KB Output is correct
15 Correct 1025 ms 132188 KB Output is correct
16 Correct 4208 ms 160488 KB Output is correct
17 Correct 6760 ms 133420 KB Output is correct
18 Correct 4349 ms 65040 KB Output is correct
19 Correct 476 ms 66144 KB Output is correct
20 Correct 1755 ms 69304 KB Output is correct
21 Correct 4271 ms 66248 KB Output is correct
22 Correct 4027 ms 131240 KB Output is correct
23 Correct 4100 ms 133496 KB Output is correct
24 Execution timed out 8096 ms 132664 KB Time limit exceeded
25 Halted 0 ms 0 KB -