Submission #558616

#	Time	Username	Problem	Language	Result	Execution time	Memory
558616		Neos	Factories (JOI14_factories)	C++14	100 / 100	5212 ms	276292 KiB

factories

#pragma GCC optimize("O3")
#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 = 20;
long long oo = 1e18 + 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*2];
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;
}

int solve(int u) {
	get_sz(u, -1); int rt = centroid(u, -1, sz[u]); done[rt] = 1;
	for (ii e: adj[rt]) if (!done[e.fi])
        par[solve(e.fi)] = rt;
	return 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-MASK(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; par[solve(0)] = -1; dfs(0);

	// preprocess LCA O(1)
    for(int j=1;MASK(j)<=_cnt;j++) {
        for(int i=1;i+MASK(j)-1<=_cnt;i++) {
            rmq[i][j] = MIN_HIGH(rmq[i][j-1], rmq[i+MASK(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[]) {
	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-MASK(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-MASK(k)+1][k]);
		minimize(res, ans[v] + d[Y[i]] + d[v] - 2 * d[_lca]);
	}
	for (int i = 0; i < S; i++) {
		int u = X[i];
		for (int v = X[i]; v >= 0; v = par[v])
			ans[v] = oo;
	}
	return res;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:138:7: warning: unused variable 'u' [-Wunused-variable]
  138 |   int u = X[i];
      |       ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67