Submission #295451

#	Time	Username	Problem	Language	Result	Execution time	Memory
295451		patrikpavic2	Factories (JOI14_factories)	C++17	100 / 100	6063 ms	240552 KiB

factories

#include "factories.h"
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef pair < int, ll > pil;
typedef pair < ll, ll > pll;

const int N = 5e5 + 500;
const int LOG = 20;

int ima[N][2], par[N][LOG], dep[N], L[N], R[N], tme, n;
ll dis[N][LOG];
vector < pii > v[N];
vector < pil > g[N];

void dfs(int x, int lst){
	L[x] = tme++;
	for(pii nxt : v[x]){
		if(nxt.X == lst) continue;
		dep[nxt.X] = dep[x] + 1;
		par[nxt.X][0] = x;
		dis[nxt.X][0] = nxt.Y;
		dfs(nxt.X, x);
	}
	R[x] = tme - 1;
}

inline bool predak(int x, int y){
	return L[x] <= L[y] && L[y] <= R[x];
}

void precompute(){
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i < n;i++){
			par[i][j] = par[par[i][j - 1]][j - 1];
			dis[i][j] = dis[i][j - 1] + dis[par[i][j - 1]][j - 1];
		}
	}
}

int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	if(predak(y, x)) return y;
	for(int i = LOG - 1;i >= 0;i--)
		if(dep[x] - dep[y] >= (1 << i))
			x = par[x][i];
	for(int i = LOG - 1;i >= 0;i--)
		if(par[x][i] != par[y][i])
			x = par[x][i],
			y = par[y][i];
	return par[x][0];
}

bool raz(int x, int y){
	return (ima[x][0] && ima[y][1]) || (ima[x][1] && ima[y][0]);
}

ll get_dis(int x, int y){
	if(!predak(x, y)) return (ll)1e18;
	ll ret = 0;
	for(int i = LOG - 1; i >= 0;i--)
		if(dep[y] - dep[x] >= (1 << i)){
			ret += dis[y][i];
			y = par[y][i];
		}
	return ret;
}

ll sol = 1e18;

pll f(int x){
	if(ima[x][0] && ima[x][1]){
		sol = min(sol, 0LL);
		return {0, 0};
	}
	pll ret = {(ll)1e18 * (!ima[x][0]), (ll)1e18 * (!ima[x][1])};
	for(pil nxt : g[x]){
		pll nov = f(nxt.X);
		nov.X += nxt.Y, nov.Y += nxt.Y;
		sol = min(sol, min(nov.X + ret.Y, nov.Y + ret.X));
		ret.X = min(ret.X, nov.X);
		ret.Y = min(ret.Y, nov.Y);
	}
	return ret;
}

void Init(int nn, int a[], int b[], int d[]) {
	n = nn;
	for(int i = 0;i + 1 < n;i++){
		v[a[i]].PB({b[i], d[i]});
		v[b[i]].PB({a[i], d[i]});
	}
	dfs(0, 0); precompute();
}

bool cmp(int x, int y){
	return L[x] < L[y];
}

ll Query(int s, int x[], int t, int y[]) {
	//printf("kverij\n");
	vector < int > sve;	
	for(int i = 0;i < s;i++){
		ima[x[i]][0] = 1;
		sve.PB(x[i]);
	}
	for(int i = 0;i < t;i++){
		ima[y[i]][1] = 1;
		sve.PB(y[i]);
	}
	sort(sve.begin(), sve.end(), cmp);
	sve.erase(unique(sve.begin(), sve.end()), sve.end());
	int m = (int)sve.size();
	for(int i = 0;i + 1 < m;i++){
		sve.PB(lca(sve[i], sve[i + 1]));
	}
	sort(sve.begin(), sve.end(), cmp);
	sve.erase(unique(sve.begin(), sve.end()), sve.end());
	m = (int)sve.size();
	stack < int > S; S.push(sve[0]);
	for(int i = 1;i < m;i++){
		while(!predak(S.top(), sve[i]))
			S.pop();
		g[S.top()].PB({sve[i], get_dis(S.top(), sve[i])});
		//printf("%d -- %lld --> %d\n", S.top(), g[S.top()].back().Y, sve[i]);
		S.push(sve[i]);
	}
	sol = 1e18; f(sve[0]);
	for(int i = 0;i < m;i++){
		ima[sve[i]][0] = 0; ima[sve[i]][1] = 0;
		g[sve[i]].clear();
	}
	return sol;
}

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