Submission #519217

#	Time	Username	Problem	Language	Result	Execution time	Memory
519217		amunduzbaev	Factories (JOI14_factories)	C++14	0 / 100	32 ms	24408 KiB

factories

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

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

#include "factories.h"
#define ar array

namespace {
	const int N = 5e5 + 5;
	const int B = 1405;
	vector<ar<int, 2>> edges[N];
	int tin[N], tout[N], t, par[N][20];
	long long d[N]; 

	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[N];
	
	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[N];
	long long dp[N], up[N];
	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[]) {
	for(int i=0;i<s;i++) is[x[i]] = 0;
	for(int i=0;i<t;i++) is[y[i]] = 0;
	
	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) return 0ll;
		is[y[i]] = 2;
	}
	
	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];
		}
		
		//~ cout<<i<<" : ";
		//~ for(auto x : ee[i]) cout<<x[0]<<" ";
		//~ cout<<"\n";
	}
	
	go(0);
	re(0);
	for(int i=0;i<m;i++){
		if(is[tmp[i]] == 2) res = min(res, dp[i]);
	}
	return res;
}

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