oj.uz

Submission #558658

# Submission time Handle Problem Language Result Execution time Memory
558658 2022-05-07T21:55:23 Z Neos Factories (JOI14_factories) C++17
100 / 100
 4970 ms 180864 KB 
#include"factories.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<int, int>;

#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class X, class Y>
	bool minimize(X &x, const Y &y) {
		X eps = 1e-9;
		if (x > y + eps) {
			x = y;
			return true;
		} else return false;
	}

template<class X, class Y>
	bool maximize(X &x, const Y &y) {
		X eps = 1e-9;
		if (x + eps < y) {
			x = y;
			return true;
		} else return false;
	}

const int N = 5e5 + 7, LOG = 21;
long long oo = 1e14 + 7;
//sample program


int n, m, sz[N], par[N];
ll ans[N], d[N];
bool done[N];
vector<ii> adj[N];

// LCA O(1)
int nodes[2*N], rmq[2*N][LOG];
int _log2[2*N]{-1}, h[N];
int cnt = 0, _cnt = 0;
int pos[N];

void get_sz(int u, int par) {
	sz[u] = 1;
	for (ii e: adj[u]) if (e.fi != par && !done[e.fi]) {
		get_sz(e.fi, u); sz[u] += sz[e.fi];
	}
}

int centroid(int u, int par, int n) {
	for (ii e: adj[u]) if (e.fi != par && !done[e.fi] && sz[e.fi] * 2 > n)
		return centroid(e.fi, u, n);
	return u;
}

void solve(int u, int pa) {
	get_sz(u, -1); int rt = centroid(u, -1, sz[u]); done[rt] = 1;
	par[rt] = pa;
	for (ii e: adj[rt]) if (!done[e.fi])
        solve(e.fi, rt);
}

void dfs(int u, int par = -1) {
	nodes[++_cnt] = u, pos[u] = _cnt; rmq[_cnt][0] = u; _log2[_cnt] = _log2[_cnt >> 1] + 1;
	for(ii e: adj[u]) if (e.fi != par) {
		d[e.fi] = d[u] + e.se;
		h[e.fi] = h[u] + 1; dfs(e.fi, u);
		nodes[++_cnt] = u; rmq[_cnt][0] = u; _log2[_cnt] = _log2[_cnt >> 1] + 1;
	}
}

#define MASK(i) (1LL<<(i))
#define MIN_HIGH(x, y) (h[x] < h[y] ? (x):(y))
int LCA(int u, int v) {
    int l = pos[u], r = pos[v];
    if(l > r) swap(l, r);
    int k = _log2[r - l + 1];
    return MIN_HIGH(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].emplace_back(ii(B[i], D[i])); adj[B[i]].emplace_back(ii(A[i], D[i]));
		ans[i] = oo;
	}
	ans[n - 1] = oo; solve(0, -1); dfs(0);

	//preprocess LCA O(1)
    for(int j = 1; j <= _log2[_cnt]; j++) {
        for(int i = 1; j <= _log2[_cnt - i + 1]; i++) {
            rmq[i][j] = MIN_HIGH(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void upd(int u, bool t) {
	for (int v = u; v >= 0; v = par[v])
		if (t) minimize(ans[v], d[u] + d[v] - 2 * d[LCA(u, v)]); else ans[v] = oo;
}

long long Query(int S, int X[], int T, int Y[]) {
    // put LCA into query function for faster
	long long res = 1e18;
	for (int i = 0; i < S; i++) {
        int u = X[i];
		for (int v = X[i]; v >= 0; v = par[v]) {
			int l = pos[u], r = pos[v];
    			if(l > r) swap(l, r);
    			int k = _log2[r - l + 1];
    			int _lca = MIN_HIGH(rmq[l][k], rmq[r - (1 << k) + 1][k]);
			minimize(ans[v], d[u] + d[v] - 2 * d[_lca]);
		}
	}
	for (int i = 0; i < T; i++)
        for (int v = Y[i]; v >= 0; v = par[v]) {
		int u = Y[i];
		int l = pos[u], r = pos[v];
    		if(l > r) swap(l, r);
    		int k = _log2[r - l + 1];
    		int _lca = MIN_HIGH(rmq[l][k], rmq[r - (1 << k) + 1][k]);
		minimize(res, ans[v] + d[Y[i]] + d[v] - 2 * d[_lca]);
	}
	for (int i = 0; i < S; i++) {
		for (int v = X[i]; v >= 0; v = par[v])
			ans[v] = oo;
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12628 KB Output is correct
2 Correct 399 ms 22332 KB Output is correct
3 Correct 553 ms 22392 KB Output is correct
4 Correct 544 ms 22252 KB Output is correct
5 Correct 536 ms 22516 KB Output is correct
6 Correct 236 ms 22256 KB Output is correct
7 Correct 560 ms 22256 KB Output is correct
8 Correct 561 ms 22304 KB Output is correct
9 Correct 545 ms 22728 KB Output is correct
10 Correct 238 ms 22252 KB Output is correct
11 Correct 545 ms 22364 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12288 KB Output is correct
2 Correct 2012 ms 151764 KB Output is correct
3 Correct 2829 ms 154524 KB Output is correct
4 Correct 815 ms 150636 KB Output is correct
5 Correct 3634 ms 180864 KB Output is correct
6 Correct 2947 ms 153908 KB Output is correct
7 Correct 1505 ms 49368 KB Output is correct
8 Correct 476 ms 49884 KB Output is correct
9 Correct 1613 ms 53416 KB Output is correct
10 Correct 1437 ms 50552 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12628 KB Output is correct
2 Correct 399 ms 22332 KB Output is correct
3 Correct 553 ms 22392 KB Output is correct
4 Correct 544 ms 22252 KB Output is correct
5 Correct 536 ms 22516 KB Output is correct
6 Correct 236 ms 22256 KB Output is correct
7 Correct 560 ms 22256 KB Output is correct
8 Correct 561 ms 22304 KB Output is correct
9 Correct 545 ms 22728 KB Output is correct
10 Correct 238 ms 22252 KB Output is correct
11 Correct 545 ms 22364 KB Output is correct
12 Correct 8 ms 12288 KB Output is correct
13 Correct 2012 ms 151764 KB Output is correct
14 Correct 2829 ms 154524 KB Output is correct
15 Correct 815 ms 150636 KB Output is correct
16 Correct 3634 ms 180864 KB Output is correct
17 Correct 2947 ms 153908 KB Output is correct
18 Correct 1505 ms 49368 KB Output is correct
19 Correct 476 ms 49884 KB Output is correct
20 Correct 1613 ms 53416 KB Output is correct
21 Correct 1437 ms 50552 KB Output is correct
22 Correct 2790 ms 151600 KB Output is correct
23 Correct 2851 ms 154144 KB Output is correct
24 Correct 4194 ms 154136 KB Output is correct
25 Correct 4181 ms 157772 KB Output is correct
26 Correct 4176 ms 154536 KB Output is correct
27 Correct 4970 ms 177480 KB Output is correct
28 Correct 1077 ms 154696 KB Output is correct
29 Correct 4118 ms 154076 KB Output is correct
30 Correct 4135 ms 153532 KB Output is correct
31 Correct 4245 ms 154228 KB Output is correct
32 Correct 1589 ms 54788 KB Output is correct
33 Correct 495 ms 50556 KB Output is correct
34 Correct 1065 ms 47652 KB Output is correct
35 Correct 1118 ms 47648 KB Output is correct
36 Correct 1441 ms 48420 KB Output is correct
37 Correct 1541 ms 48164 KB Output is correct