Submission #729791

#	Time	Username	Problem	Language	Result	Execution time	Memory
729791		NintsiChkhaidze	Factories (JOI14_factories)	C++17	0 / 100	23 ms	24028 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define s second
#define f first
#define ll long long
using namespace std;
 
const int M = 5e5 + 5;
const ll inf = 1e18;
int center,parent[M];
bool fix[M];
ll dp[M],dis[M];
vector <pair <int,ll> > v[M],g[M];
 
int findcentroid(int x,int par,int n,int weight,int &centroid,ll &edge_weight){
	int s = 1;
	for (auto [to,w]: v[x])
		if (!fix[to] && to != par) s += findcentroid(to,x,n,weight + w,centroid,edge_weight);
	
	if (centroid==-1 && (2*s >= n || par == -1)) centroid = x,edge_weight = weight;
	return s;
}
void build(int x,int par,int n,int weight){
	int centroid = -1; ll edge_weight = 0;
	findcentroid(x,-1,n,weight,centroid,edge_weight);
	fix[centroid] = 1;
	
	if (!center) center = centroid;
	else{
		g[centroid].pb({par,edge_weight});
		g[par].pb({centroid,edge_weight});
	}
	
	for (auto [to,w]: v[centroid])
		if (!fix[to]) build(to,centroid,n/2,w);
}
 
void dfs(int x,int par,ll D){
	for (auto [to,w]: g[x]){
		if (to == par) continue;
		parent[to] = x;
		dis[to] = w;
		dfs(to,x,D + w);
	}
}
void Init(int n, int A[], int B[], int D[]) {
	
	for (int i=0;i<n-1;i++){
		v[A[i] + 1].pb({B[i] + 1,D[i]});
		v[B[i] + 1].pb({A[i] + 1,D[i]});
	}
	
	for (int i = 1; i <= n; i++) dp[i] = inf;
	build(1,-1,n,0);
	parent[center] = -1;
	dfs(center,-1,0);
}
 
long long Query(int S, int X[], int T, int Y[]) {
	ll ans = 1e18;
	vector <int> v; v.clear();
	for (int i=0;i<S;i++){
		X[i]++;
		int x = X[i]; ll sum = 0;
		while (x != -1){
			dp[x] = min(dp[x],sum);
			v.pb(x);
			sum += dis[x];
			x = parent[x];
		}
	}
	
	for (int i=0;i<T;i++){
		Y[i]++;
		int y = Y[i]; ll sum = 0;
		while (y != -1){
			ans = min(ans,sum + dp[y]);
			sum += dis[y];
			y = parent[y];
		}
	}
	
	for (int x: v) dp[x] = inf;
	return ans;
}

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