Submission #558658

#	Time	Username	Problem	Language	Result	Execution time	Memory
558658		Neos	Factories (JOI14_factories)	C++17	100 / 100	4970 ms	180864 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67