Submission #700992

#	Time	Username	Problem	Language	Result	Execution time	Memory
700992		angelo_torres	Factories (JOI14_factories)	C++17	0 / 100	778 ms	524288 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll N = 5e5 + 10;
const ll M = 2e6 + 20;
const ll inf = 1e17;

int n,t[N],p[N];
ll d[N],q[N];
vector<pair<int,ll>> g[N];
deque<ll> s[N];

void dfs(int v,int f){
	t[v] = 1;
	for(auto [u,w] : g[v]){
		if(u == f) continue;
		dfs(u,v);
		t[v] += t[u];
	}
}

int find(int v,int f,int tm){
	for(auto [u,w] : g[v]){
		if(u == f) continue;
		if(t[u]*2 > tm) return find(u,v,tm);
	}
	return v;
}

void gfs(int v,int f){
	s[v].push_front(d[v]);
	for(auto [u,w] : g[v]){
		if(u == f) continue;
		d[u] = d[v] + w;
		gfs(u,v);
	}
}

void build(int v,int f){
	dfs(v,f);
	int c = find(v,f,t[v]);
	d[v] = 0, p[c] = f;
	gfs(v,f);
	for(auto [u,w] : g[c]){
		if(u == f) continue;
		build(u,c);
	}
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0; i < n; ++i){
		g[A[i]].push_back({B[i],(ll) D[i]});
		g[B[i]].push_back({A[i],(ll) D[i]});
	}
	build(0,-1);
}

long long Query(int S, int X[], int T, int Y[]){
	for(int i = 0; i < S; ++i){
		int aux = X[i], id = 0;
		while(aux != -1){
			q[aux] = min(q[aux],s[X[i]][id]);
			aux = p[aux], id++;
		}
	}
	ll ans = inf;
	for(int i = 0; i < T; ++i){
		int aux = Y[i], id = 0;
		while(aux != -1){
			ans = min(ans,q[aux]+s[Y[i]][id]);
			aux = p[aux], id++;
		}
	}
	for(int i = 0; i < S; ++i){
		int aux = X[i];
		while(aux != -1) q[aux] = inf, aux = p[aux];
	}
	return ans;
}

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