Submission #310856

#	Time	Username	Problem	Language	Result	Execution time	Memory
310856		vipghn2003	Factories (JOI14_factories)	C++14	100 / 100	2607 ms	230920 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
const int maxN = 5e5 + 7;
int n, level[maxN], st[maxN], ed[maxN], cnt = 0, now = 0, sz = 0, euler[2 * maxN], lg[2 * maxN], ft[maxN];
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN], par[20][2 * maxN];
vector < pair <int, int> > edge[maxN];
 
void dfs(int u, int p){
	st[u] = ++cnt;
	euler[++now] = u;
	ft[u] = now;
	for(pair <int, int> to : edge[u]){
		int v = to.fi, w = to.se;
		if(v == p) continue;
		level[v] = level[u] + 1;
		depth[v] = depth[u] + w;
		dfs(v, u);
		euler[++now] = u;
	}
	ed[u] = cnt;
}
 
pair <int, int> get(int l, int r){
	int add = lg[r - l + 1];
	return min(par[add][l], par[add][r - (1 << add) + 1]);
}
 
int lca(int u, int v){
	if(ft[u] > ft[v]) swap(u, v);
	return get(ft[u], ft[v]).se;
}
 
bool cmp(pair <int, int> x, pair <int, int> y){
	return st[x.fi] < st[y.fi];
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++){
		A[i]++, B[i]++;
		edge[A[i]].pb(mp(B[i], D[i]));
		edge[B[i]].pb(mp(A[i], D[i]));
	}
	level[1] = 1;
	dfs(1, 1);
	for(int i = 1; i <= now; i++) par[0][i] = mp(level[euler[i]], euler[i]);
	for(int i = 2; i <= 2 * n; i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i < 20; i++){
		for(int j = 1; j + (1 << i) - 1 <= now; j++){
			par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
		}
	}
	st[n + 1] = 1e9;
}
 
pair <long long, long long> solve(){
	int u = cur[cnt].fi;
	long long A = 1e18, B = 1e18;
	if(cur[cnt].se == 0) A = min(A, depth[u]);
	if(cur[cnt].se == 1) B = min(B, depth[u]);
	cnt++;
	if(cnt > sz) return mp(A, B);
	while(cur[cnt].fi == u){
		if(cur[cnt].se == 0) A = min(A, depth[u]);
		if(cur[cnt].se == 1) B = min(B, depth[u]);
		cnt++;
	}
	while(ed[u] >= st[cur[cnt].fi]){
		pair <long long, long long> tmp = solve();
		A = min(A, tmp.fi), B = min(B, tmp.se);
	}
	ans = min(ans, A + B - 2LL * depth[u]);
	return mp(A, B);
}
 
long long Query(int S, int X[], int T, int Y[]) {
	ans = 1e18;
	sz = 0;
	for(int i = 0; i < S; i++) cur[++sz] = mp(X[i] + 1, 0);
	for(int i = 0; i < T; i++) cur[++sz] = mp(Y[i] + 1, 1);
	sort(cur + 1, cur + 1 + sz, cmp);
	int sv = sz;
	for(int i = 1; i < sv; i++) cur[++sz] = mp(lca(cur[i].fi, cur[i + 1].fi), 2);
	cur[++sz] = mp(n + 1, 0);
	sort(cur + 1, cur + 1 + sz, cmp);
	//for(int i = 1; i <= sz; i++) cout << cur[i].fi << endl;
	cnt = 1;
	solve();
	return ans;
}

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