제출 #110695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110695		autumn_eel	공장들 (JOI14_factories)	C++14	15 / 100	3782 ms	70932 KiB

factories

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

#include "factories.h"

/*
struct SparseTable{
	SparseTable(vector<int>v){
		
	}
};
*/

int n;
vector<P>E[600000];

void Init(int N, int A[], int B[], int D[]) {
	n=N;
	rep(i,n-1){
		E[A[i]].push_back(P(D[i],B[i]));
		E[B[i]].push_back(P(D[i],A[i]));
	}
}

ll d[600000];

long long Query(int S, int X[], int T, int Y[]) {
	if(n<=5000){
		priority_queue<P,vector<P>,greater<P>>que;
		rep(i,n)d[i]=LLONG_MAX;
		rep(i,S){
			d[X[i]]=0;
			que.push(P(0,X[i]));
		}
		while(!que.empty()){
			P p=que.top();que.pop();
			if(d[p.second]!=p.first)continue;
			for(P u:E[p.second]){
				if(d[u.second]>p.first+u.first){
					d[u.second]=p.first+u.first;
					que.push(P(d[u.second],u.second));
				}
			}
		}
		ll Min=LLONG_MAX;
		rep(i,T)Min=min(Min,d[Y[i]]);
		return Min;
	}
	return -1;
}

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