oj.uz

답안 #1086270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086270 2024-09-09T22:28:58 Z 4QT0R 공장들 (JOI14_factories) C++17
18 / 100
 8000 ms 189524 KB 
#include <bits/stdc++.h>
#include "factories.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-1; 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<=1300 && T<=1300){
		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 [d,v] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 12632 KB Output is correct
2 Execution timed out 8069 ms 30804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 1441 ms 155184 KB Output is correct
3 Correct 3392 ms 158288 KB Output is correct
4 Correct 857 ms 152524 KB Output is correct
5 Correct 3103 ms 189524 KB Output is correct
6 Correct 2407 ms 160464 KB Output is correct
7 Correct 6013 ms 59732 KB Output is correct
8 Correct 1445 ms 59404 KB Output is correct
9 Correct 4019 ms 64256 KB Output is correct
10 Correct 3548 ms 61008 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 12632 KB Output is correct
2 Execution timed out 8069 ms 30804 KB Time limit exceeded
3 Halted 0 ms 0 KB -