Submission #1100161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100161		Nurislam	Factories (JOI14_factories)	C++17	15 / 100	8076 ms	77980 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);
int sz;
void Init(int N, int A[], int B[], int D[]) {
	sz = N;
	for(int i = 0; i < N-1; i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
}
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;
long long Query(int S, int X[], int T, int Y[]) {
	q = priority_queue<array<ll,2>> ();
	set<int> rem;
	set<int> st;
	for(int i = 0; i < T; i++){
		st.insert(Y[i]);
	}
	for(int i = 0; i < S; i++){
		q.push({0, X[i]});
		dif[X[i]] = 0;
		rem.insert(X[i]);
	}
	while(q.size()){
		auto [dis, ps] = q.top();
		q.pop();
		//cout << dis << ' ' << ps << '\n';
		dis = abs(dis);
		if(dif[ps] < dis)continue;
		if(st.count(ps)){
			//for(int i = 0; i < sz; i++){
				//cout << dif[i]  << ' ' << i << '\n';
			//}
			//cout << '\n';
			for(auto i:rem)dif[i] = inf;
			return dis;
		}
		//cout << ps << '\n';
		for(auto &[to, d]:g[ps]){
			//cout << to << ' ' << d << '\n';
			if(chmin(dif[to], dif[ps] + d)){
				rem.insert(to);
				q.push({-dif[to], to});
			}
		}
	}
	
	
	return inf;
}

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