oj.uz

Submission #700992

# Submission time Handle Problem Language Result Execution time Memory
700992 2023-02-19T15:48:54 Z angelo_torres Factories (JOI14_factories) C++17
0 / 100
 778 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 719 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 778 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 719 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -