Submission #1100456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100456		Nurislam	Factories (JOI14_factories)	C++17	100 / 100	7599 ms	248084 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<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];
}
ll get(int a,int b){
	if(a == b)return 0;
	int l = lca(a, b);
	return ds[a] + ds[b] - 2*ds[l];
}
vector<int> vs(n, 0);
vector<int> have;
vector<int> sub(n, 0);
vector<vector<int>> par(n);
vector<ll> res(n,inf);
int ns;
void clacS(int v, int pr){
	sub[v] = 1;
	have.pb(v);
	for(auto [to, d]:g[v]){
		if(vs[to] || to == pr)continue;
		clacS(to, v);
		sub[v] += sub[to];
	}
}

int centr(int ps, int pr){
	for(auto [to, d]:g[ps]){
		if(vs[to] || to == pr)continue;
		if(sub[to] > ns/2)return centr(to, ps);
	}
	return ps;
}


void decm(int ps){
	have.clear();
	clacS(ps, ps);
	ns = sub[ps];
	int cur = centr(ps, ps);
	for(auto v:have){
		par[v].pb(cur);
	}
	vs[cur] = 1;
	for(auto [to,d]:g[cur]){
		if(vs[to])continue;
		decm(to);
	}
}





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);
	decm(0);
}
long long Query(int S, int X[], int T, int Y[]) {
	vector<int> tod;
	for(int i = 0; i < S; i++){
		//cout << X[i] << ":\n";
		for(auto v:par[X[i]]){
			//cout << v << ' ';
			chmin(res[v], get(v, X[i]));
			//cout << get(v, X[i]) << '\n';
			tod.pb(v);
		}
		//cout << '\n';
	}
	ll ans = inf;
	for(int i = 0; i < T; i++){
		for(auto v:par[Y[i]]){
			chmin(ans, res[v] + get(v, Y[i]));
		}
	}
	for(auto x:tod)res[x] = inf;
	return ans;
}
	
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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