Submission #573182

#	Time	Username	Problem	Language	Result	Execution time	Memory
573182		Arnch	Factories (JOI14_factories)	C++17	15 / 100	8051 ms	83352 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e18, maxn = 1e6 + 10;

int n;
ll d[maxn];
bool mark[maxn];
vector<pair<int, int> > G[maxn];

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		G[A[i]].push_back({B[i], D[i]});
		G[B[i]].push_back({A[i], D[i]});
	}
	for(int i = 0; i < n; i++) d[i] = inf;
}

long long Query(int S, int X[], int T, int Y[]) {
	set<pair<ll, int> > st;
	vector<int> vc;
	for(int i = 0; i < S; i++) {
		d[X[i]] = 0;
		st.insert({0, X[i]});
		vc.push_back(X[i]);
	}
	for(int i = 0; i < T; i++) mark[Y[i]] = 1;
	ll ans = 0;
	while(!st.empty()) {
		int p = st.begin() -> second; st.erase(st.begin());
		if(mark[p]) {
			ans = d[p];
			break;
		}
		for(auto i : G[p]) {
			if(d[i.first] > d[p] + i.second) {
				st.erase({d[i.first], i.first});
				d[i.first] = d[p] + i.second;
				st.insert({d[i.first], i.first});
				vc.push_back(i.first);
			}
		}
	}

	for(auto i : vc) d[i] = inf;
	for(int i = 0; i < T; i++) mark[Y[i]] = 0;

	return ans;
}

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