oj.uz

Submission #1086267

# Submission time Handle Problem Language Result Execution time Memory
1086267 2024-09-09T22:11:33 Z 4QT0R Factories (JOI14_factories) C++17
18 / 100
 6067 ms 189656 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll oo=1e18;
vector<pair<int,ll>> graph[500003];
ll dep[500003];
ll real_dep[500003];
ll jmp[500003][20];

int lca(int a, int b){
	if (dep[a]<dep[b])swap(a,b);
	for (int i = 19; i>=0; i--){
		if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
	}
	if (a==b)return a;
	for (int i = 19; i>=0; i--){
		if (jmp[a][i]!=jmp[b][i]){
			a=jmp[a][i];
			b=jmp[b][i];
		}
	}
	return jmp[a][0];
}

ll dist(int a, int b){
	return real_dep[a]+real_dep[b]-2*real_dep[lca(a,b)];
}

void prep(int v, int p){
	jmp[v][0]=p;
	for (int i = 1; i<20; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
	for (auto [u,d] : graph[v]){
		if (u==p)continue;
		dep[u]=dep[v]+1;
		real_dep[u]=real_dep[v]+d;
		prep(u,v);
	}
}

int n;

void Init(int N, int A[], int B[], int D[]){
	n=N;
	for (int i = 0; i<N; i++){
		graph[A[i]].push_back({B[i],D[i]});
		graph[B[i]].push_back({A[i],D[i]});
	}
	prep(0,0);
}

ll odl[500003];
bool fin[500003];

ll Query(int S, int X[], int T, int Y[]){
	if (S<=1200 && T<=1200){
		ll ans=oo;
		for (int i = 0; i<S; i++){
			for (int j = 0; j<T; j++){
				ans=min(ans,dist(X[i],Y[j]));
			}
		}
		return ans;
	}
	for (int i = 0; i<T; i++)fin[Y[i]]=true;
	fill(odl,odl+n,oo);
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	for (int i = 0; i<S; i++){
		odl[X[i]]=0;
		pq.push({0,X[i]});
	}
	while(pq.size()){
		auto [v,d] = pq.top();
		pq.pop();
		if (d>odl[v])continue;
		if (fin[v]){
			for (int i = 0; i<T; i++)fin[Y[i]]=false;
			return d;
		}
		for (auto [u,x] : graph[v]){
			if (d+x<odl[u]){
				odl[u]=d+x;
				pq.push({odl[u],u});
			}
		}
	}
	return -1;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 12632 KB Output is correct
2 Runtime error 139 ms 52512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 1376 ms 155400 KB Output is correct
3 Correct 3352 ms 158392 KB Output is correct
4 Correct 885 ms 152724 KB Output is correct
5 Correct 3233 ms 189656 KB Output is correct
6 Correct 2518 ms 160436 KB Output is correct
7 Correct 6067 ms 59728 KB Output is correct
8 Correct 1423 ms 59552 KB Output is correct
9 Correct 4098 ms 64412 KB Output is correct
10 Correct 3594 ms 61188 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 12632 KB Output is correct
2 Runtime error 139 ms 52512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -