Submission #1255924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255924		kamrad	Factories (JOI14_factories)	C++20	100 / 100	7220 ms	243648 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

using ll  = long long;
using pii = pair<ll, ll>;

#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);

const ll LG     = 30;
const ll Inf    = 2e18 + 10;
const ll maxN   = 5e5 + 10;

ll n;
ll timer = 1;
ll h[maxN];
ll d[maxN];
ll st[maxN];
ll ft[maxN];
ll par[maxN][LG];

vector <pii> neighb[maxN];

struct SegTree {
	struct Node {
		ll mn;
		Node() {
			mn = Inf;
		}
	} t[maxN<<2];

	void update(ll id, ll L, ll R, ll idx, ll val) {
		if(L+1 == R) {
			t[id].mn = val;
			return;
		}
		ll mid = (L+R)>>1;
		if(idx < mid)
			update(2*id+0, L, mid, idx, val);
		else
			update(2*id+1, mid, R, idx, val);
		t[id].mn = min(t[2*id+0].mn, t[2*id+1].mn);
	}

	ll get(ll id, ll L, ll R, ll l, ll r) {
		if(L == l and R == r)
			return t[id].mn;

		ll ret = Inf;
		ll mid = (L+R)>>1;
		if(l < mid)
			minr(ret, get(2*id+0, L, mid, l, min(mid, r)));
		if(r > mid)
			minr(ret, get(2*id+1, mid, R, max(l, mid), r));
		return ret;
	}
} s, t;

void dfs(ll u) {
	st[u] = timer++;
	for(ll i = 1; i < LG; i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for(auto [v, w] : neighb[u]) {
		if(v != par[u][0]) {
			h[v] = h[u]+1;
			d[v] = d[u]+w;
			par[v][0] = u;
			dfs(v);
		}
	}
	ft[u] = timer;
}

ll LCA(ll u, ll v) {
	if(h[u] > h[v])
		swap(u, v);

	for(ll i = LG-1; i >= 0; i--)
		if(h[par[v][i]] >= h[u])
			v = par[v][i];

	if(u == v)
		return v;

	for(ll i = LG-1; i >= 0; i--) {
		if(par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(ll i = 0; i < n-1; i++) {
		neighb[A[i]+1].pb({B[i]+1, D[i]});
		neighb[B[i]+1].pb({A[i]+1, D[i]});
	}
	h[1] = 1;
	dfs(1);
}

bool cmp(ll u, ll v) {
	return st[u] < st[v];
}

long long Query(int S, int X[], int T, int Y[]) {
	set <ll> virt;
	vector <ll> val;

	for(ll i = 0; i < S; i++) {
		val.pb(X[i]+1);
		s.update(1, 1, n+1, st[X[i]+1], d[X[i]+1]);
	}
	for(ll i = 0; i < T; i++) {
		val.pb(Y[i]+1);
		t.update(1, 1, n+1, st[Y[i]+1], d[Y[i]+1]);
	}

	sort(all(val), cmp);

	for(ll i = 0; i < sz(val)-1; i++)
		virt.insert(LCA(val[i], val[i+1]));
	
	ll ans = Inf;
	for(auto x : virt) {
		ll tmp = s.get(1, 1, n+1, st[x], ft[x]);
		tmp += t.get(1, 1, n+1, st[x], ft[x]);
		tmp -= 2*d[x];
		minr(ans, tmp);
	}
	
	for(ll i = 0; i < S; i++)
		s.update(1, 1, n+1, st[X[i]+1], Inf);
	for(ll i = 0; i < T; i++)
		t.update(1, 1, n+1, st[Y[i]+1], Inf);
	return ans;
}

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