Submission #44219

#	Time	Username	Problem	Language	Result	Execution time	Memory
44219		szawinis	Factories (JOI14_factories)	C++17	0 / 100	6072 ms	76584 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;

struct ST {
	int n;
	vector<ll> t;
	ST() {}
	ST(int n): n(n) { t.assign(2*n, INF); }
	void update(int i, ll v) {
		for(t[i += n] = v; i > 1; i >>= 1) t[i>>1] = min(t[i], t[i^1]);
	}
	ll query(int l, int r) {
		ll res = INF;
		for(l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) res = min(t[l++], res);
			if(r & 1) res = min(t[--r], res);
		}
		return res;
	}
} stup, stdown;

int n;
vector<vector<pair<int,int> > > g;
vector<int> sz, in, out, par, nxt, pre;
vector<ll> d;
void dfs_sz(int u = 0) {
	sz[u] = 1;
	for(auto p: g[u]) {
		int v, w; tie(v, w) = p;
		if(v == par[u]) continue;
		d[v] = d[u] + w;
		par[v] = u;
		dfs_sz(v);
		sz[u] += sz[v];
	}
	for(auto &p: g[u])
		if(g[u].front().first == par[u] || sz[p.first] > sz[g[u].front().first])
			swap(p, g[u].front());
	if(g[u].size() > 1) pre[u] = pre[g[u].front().first];
	else pre[u] = u;
}

void dfs_hld(int u = 0) {
	static int curr_t = 0;
	in[u] = curr_t++;
	for(auto p: g[u]) {
		int v, w; tie(v, w) = p;
		if(v == par[u]) continue;
		nxt[v] = (v == g[u].front().first ? nxt[u] : v);
		dfs_hld(v);
	}
	out[u] = curr_t - 1;
	// cout << u << ' ' << d[u] << ' ' << nxt[u] << endl;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	g.resize(n);
	sz.resize(n), in.resize(n), out.resize(n), par.resize(n), nxt.resize(n), pre.resize(n);
	d.resize(n);
	stup = ST(n), stdown = ST(n);
	for(int i = 0; i < n-1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	par[0] = -1;
	dfs_sz();
	dfs_hld();
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ret = INF;
	for(int i = 0; i < S; i++) {
		for(int v = X[i]; v != -1; v = par[nxt[v]]) {
			stup.update(in[v], min(stup.t[n+in[v]], d[X[i]] - 2*d[v]));
			stdown.update(in[v], min(stdown.t[n+in[v]], d[X[i]]));
		}
	}
	for(int i = 0; i < T; i++) {
		// ret = min(stdown.query(in[Y[i]], out[Y[i]]) - d[Y[i]], ret);
		for(int v = Y[i]; v != -1; v = par[nxt[v]]) {
			ret = min(stup.query(in[nxt[v]], in[v]) + d[Y[i]], ret);
			ret = min(stdown.query(in[v], in[pre[v]]) + d[Y[i]] - 2*d[v], ret);
		}
	}
	for(int i = 0; i < S; i++) {
		for(int v = X[i]; v != -1; v = par[nxt[v]]) {
			stup.update(in[v], INF);
			stdown.update(in[v], INF);
		}
	}
	return ret;
}

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