oj.uz

Submission #729791

# Submission time Handle Problem Language Result Execution time Memory
729791 2023-04-24T14:49:01 Z NintsiChkhaidze Factories (JOI14_factories) C++17
0 / 100
 23 ms 24028 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24028 KB Output isn't correct
2 Halted 0 ms 0 KB -