Submission #308747

#	Time	Username	Problem	Language	Result	Execution time	Memory
308747		pit4h	Factories (JOI14_factories)	C++14	100 / 100	6925 ms	229804 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
/*#ifndef LOCAL
#define cerr if(0)cerr
#endif
*/
#define st first
#define nd second
using namespace std;
using ll = long long;
const int MAXN = 5e5+1;
const ll INF = 1e16+1;
vector<pair<int, int>> g[MAXN];
ll h[MAXN];
vector<int> euler, positions[MAXN];
int l[MAXN], r[MAXN];
void dfs(int x, int p) {
	euler.push_back(x);
	l[x] = r[x] = euler.size()-1;
	for(auto i: g[x]) {
		if(i.st != p) {
			h[i.st] = h[x] + i.nd;
			dfs(i.st, x);
			euler.push_back(x);
			r[x] = euler.size()-1;
		}
	}
}
struct Segtree {
	vector<pair<ll, int>> tree;
	int base;
	vector<int> history;
	void init(int sz) {
		base=1;
		while(base<sz) base *= 2;
		tree.resize(2*base+1, {INF, -1});
	}
	void ins(int pos, pair<ll, int> val) {
		history.push_back(pos);
		pos += base;
		while(pos) {
			tree[pos] = min(tree[pos], val);	
			pos /= 2;
		}
	}
	void del(int pos) {
		pos += base;
		while(pos) {
			tree[pos] = {INF, -1};
			pos /= 2;
		}
	}
	void clr() {
		for(int i: history) del(i);
		history.clear();
	}
	int query(int L, int R) {
		L += base;
		R += base;
		pair<ll, int> res = min(tree[L], tree[R]);
		while(L/2 != R/2) {
			if(L%2==0) {
				res = min(res, tree[L+1]);
			}
			if(R%2==1) {
				res = min(res, tree[R-1]);
			}
			L /= 2;
			R /= 2;
		}
		return res.nd;
	}
};
Segtree Tree, Ts, Tt;
int LCA(int x, int y) {
	return Tree.query(min(l[x], l[y]), max(r[x], r[y]));
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0; i<N-1; ++i) {
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0);
	Tree.init(euler.size());
	for(int i=0; i<(int)euler.size(); ++i) {
		positions[euler[i]].push_back(i);
		Tree.ins(i, {h[euler[i]], euler[i]});
	}
	Ts.init(euler.size());
	Tt.init(euler.size());
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pair<int, int>> vec;
	for(int i=0; i<S; ++i) {
		vec.push_back({l[X[i]], X[i]});
		for(int j: positions[X[i]]) {
			Ts.ins(j, {h[X[i]], X[i]});
		}
	}
	for(int i=0; i<T; ++i) {
		vec.push_back({l[Y[i]], Y[i]});
		for(int j: positions[Y[i]]) {
			Tt.ins(j, {h[Y[i]], Y[i]});
		}
	}
	sort(vec.begin(), vec.end());
	ll ans = INF;
	vector<int> nodes;
	for(int i=1; i<(int)vec.size(); ++i) {
		int lca = LCA(vec[i-1].nd, vec[i].nd);
		nodes.push_back(lca);
	}
	for(int lca: nodes) {
		int it1 = Ts.query(l[lca], r[lca]), it2 = Tt.query(l[lca], r[lca]);
		if(it1 == -1 || it2 == -1) continue;
		ans = min(ans, h[it1] + h[it2] - 2*h[lca]);
	}
	Ts.clr();
	Tt.clr();
	return ans;
}

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