Submission #971882

#	Time	Username	Problem	Language	Result	Execution time	Memory
971882		ByeWorld	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4014 ms	49516 KiB

plan

#include <bits/stdc++.h>
#include <random>
#define ll long long
#define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e6+10;
const int INF = 2e9+10;
const int LOG = 30;
const int MOD = 1e9+7;

int n, m, K, Q;
vector <pii> adj[MAXN];
vector <int> vec;
int dis[MAXN], val[MAXN];

priority_queue <pii, vector<pii>, greater<pii>> pq;
void dji(){
	for(int i=1; i<=n; i++) val[i] = INF;
	for(auto in : vec){
		val[in] = 0;
		pq.push({0, in});
	}
	while(!pq.empty()){
		int nw = pq.top().se, dist = pq.top().fi;
		pq.pop();
		// cout << nw << " dist\n";
		if(val[nw] < dist) continue;
		for(auto ed : adj[nw]){
			int nx = ed.fi, wei = ed.se;
			if(val[nx] > val[nw]+wei){
				val[nx] = val[nw]+wei;
				pq.push({val[nx],nx});
			}
		}
	}
}

bool vis[MAXN];
int en, num;
bool cek(int nw){
	if(nw == en) return 1;
	vis[nw] = 1;
	// cout << nw << " nw\n";
	bool can = 0;
	for(auto ed : adj[nw]){
		int nx = ed.fi;
		if(!vis[nx] && val[nx]>=num) can |= cek(nx);
	}
	return can;
}

signed main() {
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int x, y, w; cin >> x >> y >> w;
		adj[x].pb({y, w}); adj[y].pb({x, w});
	}
	cin >> K;
	for(int i=1; i<=K; i++){
		int p; cin >> p;
		vec.pb(p);
	}
	dji();
	// for(int i=1; i<=n; i++) cout << val[i] << " \n"[i==n];
	cin >> Q;
	while(Q--){
		int x; cin >> x >> en;
		int l=0, r=val[x], mid=0, cnt=-1;
		while(l<=r){
			mid = md; num = mid;
			for(int i=1; i<=n; i++) vis[i] = 0;
			if(cek(x)){
				l = mid+1; cnt = mid;
			} else r = mid-1;
		}
		cout << cnt << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46