Submission #1312739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312739		crispxx	Factories (JOI14_factories)	C++20	100 / 100	2500 ms	159868 KiB

factories

#include "factories.h"

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

using ll = long long;

const ll inf = 1e18;

vector<vector<array<ll, 2>>> adj;

vector<vector<int>> jmp;

vector<int> tin, tout;

vector<bool> sn, tn;

vector<ll> d, mxs, mxt, rs, rt;

bool cmp(int u, int v) {
	return tin[u] < tin[v];
}

bool upper(int u, int v) {
	return tin[v] >= tin[u] && tout[v] <= tout[u];
}

bool chmin(ll &a, const ll &b) {
	return a > b ? a = b, true : false;
}

bool chmax(ll &a, const ll &b) {
	return a < b ? a = b, true : false;
}

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

void Init(int n, int a[], int b[], int D[]) {
	adj.resize(n);
	jmp.resize(n);
	sn.resize(n);
	tn.resize(n);
	mxs.resize(n);
	mxt.resize(n);
	rs.resize(n);
	rt.resize(n);
	tin.resize(n);
	tout.resize(n);
	d.resize(n);
	
	for(int i = 0; i < n; i++) {
		jmp[i].resize(20);
	}
	
	for(int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back({b[i], D[i]});
		adj[b[i]].push_back({a[i], D[i]});
	}
	
	int timer = 0;
	
	auto dfs = [&](auto &&self, int v, int p) -> void {
		jmp[v][0] = p;
		
		for(int i = 1; i < 20; i++) {
			jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
		}
		
		tin[v] = ++timer;
		
		for(auto [to, c] : adj[v]) {
			if(to == p) continue;
			
			d[to] = d[v] + c;
			
			self(self, to, v);
		}
		
		tout[v] = timer;
	};
	
	dfs(dfs, 0, 0);
	
	for(int i = 0; i < n; i++) {
		adj[i].clear();
	}
}

long long Query(int s, int x[], int t, int y[]) {
	vector<int> ver;
	
	for(int i = 0; i < s; i++) {
		ver.push_back(x[i]);
	}
	
	for(int i = 0; i < t; i++) {
		ver.push_back(y[i]);
	}
	
	sort(ver.begin(), ver.end(), cmp);
	
	for(int i = 0; i + 1 < s + t; i++) {
		ver.push_back( lca(ver[i], ver[i + 1]) );
	}
	
	sort(ver.begin(), ver.end(), cmp);
	ver.erase(unique(ver.begin(), ver.end()), ver.end());
	
	for(auto &v : ver) {
		adj[v].clear();
		sn[v] = tn[v] = false;
		mxs[v] = mxt[v] = rs[v] = rt[v] = inf;
	}
	
	for(int i = 0; i < s; i++) {
		sn[x[i]] = true;
	}
	
	for(int i = 0; i < t; i++) {
		tn[y[i]] = true;
	}
	
	stack<int> st;
	
	for(int i = 0; i < (int)ver.size(); i++) {
		while(!st.empty() && !upper(st.top(), ver[i])) {
			st.pop();
		}
		
		if(!st.empty()) {
			adj[st.top()].push_back({ver[i], d[ver[i]] - d[st.top()]});
		}
		
		st.push(ver[i]);
	}
	
	// cout << "edges: " << '\n';
	
	// for(auto v : ver) {
		// for(auto [to, c] : adj[v]) {
			// cout << v << ' ' << to << ' ' << c << '\n';
		// }
	// }
	
	{
		auto dfs = [&](auto &&self, int v) -> void {
			if(sn[v]) mxs[v] = d[v];
			if(tn[v]) mxt[v] = d[v];
			
			for(auto [to, c] : adj[v]) {
				self(self, to);
				
				chmin(mxs[v], mxs[to]);
				chmin(mxt[v], mxt[to]);
			}
		};
		
		dfs(dfs, ver[0]);
	}
	
	ll ans = inf;
	
	{
		auto dfs = [&](auto &&self, int v) -> void {
			if(sn[v]) {
				chmin(ans, min(rt[v], mxt[v] - d[v]));
			}
			
			if(tn[v]) {
				chmin(ans, min(rs[v], mxs[v] - d[v]));
			}
			
			int m = adj[v].size();
			
			vector<array<ll, 2>> suf(m + 1, {inf, inf});
			
			for(int i = m - 1; i >= 0; i--) {
				auto [to, c] = adj[v][i];
				suf[i][0] = min(suf[i + 1][0], mxs[to]);
				suf[i][1] = min(suf[i + 1][1], mxt[to]);
			}
			
			array<ll, 2> pref{inf, inf};
			
			for(int i = 0; i < m; i++) {
				auto [to, c] = adj[v][i];
				rs[to] = c + min({rs[v], suf[i + 1][0] - d[v], pref[0] - d[v]});
				rt[to] = c + min({rt[v], suf[i + 1][1] - d[v], pref[1] - d[v]});
				chmin(pref[0], mxs[to]);
				chmin(pref[1], mxt[to]);
				self(self, to);
			}
		};
		
		dfs(dfs, ver[0]);
	}
	
	return ans;
}

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