Submission #519219

#	Time	Username	Problem	Language	Result	Execution time	Memory
519219		amunduzbaev	Factories (JOI14_factories)	C++14	100 / 100	2664 ms	161304 KiB

factories

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#include "factories.h"
#define ar array

const int M = 5e5 + 5;
vector<ar<int, 2>> edges[M];
int tin[M], tout[M], t, par[M][20];
long long d[M]; 

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto x : edges[u]){
		if(x[0] == p) continue;
		d[x[0]] = d[u] + x[1];
		par[x[0]][0] = u;
		dfs(x[0], u);
	} tout[u] = t;
}

int is[M];

bool iis(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
	if(iis(a, b)) return a;
	if(iis(b, a)) return b;
	//~ cout<<tin[1]<<" "<<tout[1]<<" "<<tin[6]<<" "<<tout[6]<<"\n";
	for(int i=19;~i;i--){
		if(!iis(par[a][i], b)) a = par[a][i];
	} // cout<<a<<"\n";
	return par[a][0];
}

vector<int> tmp;
vector<ar<long long, 2>> ee[M];
long long dp[M], up[M];

void go(int u, int p = -1){
	if(is[tmp[u]] == 1) dp[u] = 0;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		go(x[0], u);
		dp[u] = min(dp[u], dp[x[0]] + x[1]);
	} // cout<<u<<" "<<dp[u]<<"\n";
}

void re(int u, int p = -1){
	if(p == -1) up[u] = 1e18;
	dp[u] = min(dp[u], up[u]);
	if(is[tmp[u]] == 1) up[u] = 0;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		up[x[0]] = up[u];
		up[u] = min(up[u], dp[x[0]] + x[1]);
	}
	
	reverse(ee[u].begin(), ee[u].end());
	up[u] = 1e18;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		up[x[0]] = min(up[x[0]], up[u]);
		up[u] = min(up[u], dp[x[0]] + x[1]);
		up[x[0]] += x[1];
		re(x[0], u);
	}
}

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

long long Query(int s, int x[], int t, int y[]) {
	if(s < t) swap(s, t), swap(x, y);
	for(int i=0;i<s;i++){
		is[x[i]] = 1;
	}
	
	long long res = 1e18;
	for(int i=0;i<t;i++){
		if(is[y[i]] == 1) res = 0;
		is[y[i]] = 2;
	}
	
	if(!res){
		for(int i=0;i<s;i++) is[x[i]] = 0;
		for(int i=0;i<t;i++) is[y[i]] = 0;
		return res;
	}
	
	tmp.clear();
	for(int i=0;i<s;i++) tmp.push_back(x[i]);
	for(int i=0;i<t;i++) tmp.push_back(y[i]);
	sort(tmp.begin(), tmp.end(), [&](int i, int j) { return (tin[i] < tin[j]); });
	int m = (int)tmp.size();
	for(int i=1;i<m;i++){
		tmp.push_back(lca(tmp[i-1], tmp[i]));
		//~ cout<<tmp[i-1]<<" "<<tmp[i]<<" "<<lca(tmp[i-1], tmp[i])<<"\n";
	}
	
	sort(tmp.begin(), tmp.end(), [&](int i, int j) { 
		if(tin[i] != tin[j]) return (tin[i] < tin[j]); 
		return tout[i] > tout[j];
	});
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	
	//~ for(auto x : tmp) cout<<x<<" ";
	//~ cout<<"\n";
	
	m = (int)tmp.size();
	vector<int> nxt(m);
	for(int i=0;i<m;i++){
		int l = i + 1, r = m;
		while(l < r){
			int m = (l + r) >> 1;
			if(tin[tmp[m]] <= tout[tmp[i]]) l = m + 1;
			else r = m;
		}
		
		nxt[i] = l;
		ee[i].clear();
		dp[i] = 1e18;
	}
	
	//~ for(int i=0;i<m;i++) cout<<nxt[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<m;i++){
		int j = i + 1;
		while(j < nxt[i]){
			ee[i].push_back({j, d[tmp[j]] - d[tmp[i]]});
			j = nxt[j];
		}
	}
	
	go(0);
	re(0);
	for(int i=0;i<m;i++){
		if(is[tmp[i]] == 2) res = min(res, dp[i]);
	}
	for(int i=0;i<m;i++) is[tmp[i]] = 0;
	return res;
}

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