Submission #1100176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100176		Nurislam	Factories (JOI14_factories)	C++17	33 / 100	8064 ms	137124 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;

	vector<vector<int> > lc(22, vector<int> (n, 0));
	vector<ll> ds(n, 0), tin(n),tout(n);
	int tim = 0;
	void dfs(int ps, int pr){
		lc[0][ps] = pr;
		for (int i = 1; i < 22; i++)
		{
			lc[i][ps] = lc[i-1][lc[i-1][ps]];
		}
		tin[ps] = tim++;
		for(auto [to, d]:g[ps]){
			if(to == pr)continue;
			ds[to] = ds[ps] + d;
			dfs(to, ps);
		}
		tout[ps] = tim++;
		
	}
	int lca (int a, int b){
		if(tin[a] < tin[b] && tout[b] < tout[a])return a;
		if(tin[b] < tin[a] && tout[a] < tout[b])return b;
		for(int i = 20; i >= 0; i--){
			int na = lc[i][a];
			if(tin[na] < tin[b] && tout[b] < tout[na])continue;
			a = na;
		}
		return lc[0][a];
	}
	
void Init(int N, int A[], int B[], int D[]) {
	
	for(int i = 0; i < N-1; i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	dfs(0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
	if(S*T >= 1000){
		if(S<T)swap(S,T),swap(X,Y);
		q = priority_queue<array<ll,2>> ();
		set<int> rem;
		set<int> st;
		for(int i = 0; i < T; i++){
			st.insert(Y[i]);
		}
		for(int i = 0; i < S; i++){
			q.push({0, X[i]});
			dif[X[i]] = 0;
			rem.insert(X[i]);
		}
		while(q.size()){
			auto [dis, ps] = q.top();
			q.pop();
			dis = abs(dis);
			if(dif[ps] < dis)continue;
			if(st.count(ps)){
				for(auto i:rem)dif[i] = inf;
				return dis;
			}
			for(auto &[to, d]:g[ps]){
				if(chmin(dif[to], dif[ps] + d)){
					rem.insert(to);
					q.push({-dif[to], to});
				}
			}
		}
	}else{
		ll ans = inf;
		for(int i = 0; i < S; i++){
			for(int j = 0; j < T; j++){
				int l = lca(X[i],Y[j]);
				chmin(ans, ds[X[i]]+ds[Y[j]]-2*ds[l]);
			}
		}
		return ans;
	}
	return inf;
}
	

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