Submission #93473

#	Time	Username	Problem	Language	Result	Execution time	Memory
93473		Dat160601	Factories (JOI14_factories)	C++14	33 / 100	8042 ms	128904 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], par[20][maxN], st[maxN], ed[maxN], cnt = 0, sz = 0;
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN];
vector < pair <int, int> > edge[maxN];

void dfs(int u, int p){
	st[u] = ++cnt;
	for(pair <int, int> to : edge[u]){
		int v = to.fi, w = to.se;
		if(v == p) continue;
		par[0][v] = u;
		level[v] = level[u] + 1;
		depth[v] = depth[u] + w;
		dfs(v, u);
	}
	ed[u] = cnt;
}

int lca(int u, int v){
	if(level[u] > level[v]) swap(u, v);
	for(int i = 19; i >= 0; i--) if(level[par[i][v]] >= level[u]) v = par[i][v];
	for(int i = 19; i >= 0; i--) if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
	if(u == v) return u;
	return par[0][u];
}

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]));
	}
	par[0][1] = 1;
	level[1] = 1;
	dfs(1, 1);
	for(int i = 1; i < 20; i++){
		for(int j = 1; j <= n; j++){
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	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: 0 / 67