Submission #729806

#	Time	Username	Problem	Language	Result	Execution time	Memory
729806		NintsiChkhaidze	Factories (JOI14_factories)	C++17	100 / 100	4328 ms	181156 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 + 5;
int parent[M],dep[M];
bool fix[M];
ll dp[M],dis[25][M];
vector <pair <int,ll> > v[M],path;
 
int findcentroid(int x,int par,int n,int &centroid,int h){
	int s = 1;
	for (auto [to,w]: v[x])
		if (!fix[to] && to != par) s += findcentroid(to,x,n,centroid,h);
		
	if (centroid==-1 && (2*s >= n || par == -1)) centroid = x;
	return s;
}
void dfs(int x,int par,int h){
	for (auto [to,w]: v[x]){
		if (!fix[to] && to != par){
			dis[h][to] = dis[h][x] + w;
			dfs(to,x,h);
		}
	}
}
void build(int x,int par,int n,int h){
	int centroid = -1; ll edge_weight = 0;
	findcentroid(x,-1,n,centroid,h);
	
	fix[centroid] = 1;
	parent[centroid] = par;
	dep[centroid] = h;
	dfs(centroid,-1,h);
	
	for (auto [to,w]: v[centroid])
		if (!fix[to]) build(to,centroid,n/2,h + 1);
}
 
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,1);
}

long long Query(int S, int X[], int T, int Y[]) {
	ll ans = inf;
	vector <int> v; v.clear();
	for (int i=0;i<S;i++){
		X[i]++;
		int x = X[i];
		while (x != -1){
			dp[x] = min(dp[x], dis[dep[x]][X[i]]);
			v.pb(x);
			x = parent[x];
		}
	}
	
	for (int i=0;i<T;i++){
		Y[i]++;
		int y = Y[i]; 
		while (y != -1){
			ans = min(ans,dis[dep[y]][Y[i]] + dp[y]);
			y = parent[y];
		}
	}
	
	for (int x: v) dp[x] = inf;
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void build(int, int, int, int)':
factories.cpp:33:24: warning: unused variable 'edge_weight' [-Wunused-variable]
   33 |  int centroid = -1; ll edge_weight = 0;
      |                        ^~~~~~~~~~~

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