Submission #495067

#	Time	Username	Problem	Language	Result	Execution time	Memory
495067		Ierus	Evacuation plan (IZhO18_plan)	C++17	19 / 100	1176 ms	70260 KiB

plan

#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
int n, m;
vector<pair<int,int>> g[N];
vector<int> d(N, INT_MAX);
int get(int _start, int _end){
	vector<int> res(n+1,-INT_MAX);
	res[_start] = d[_start];
	set<pair<int,int>> st = {{-res[_start], _start}};
	while(!st.empty()){
		int v = st.begin() -> S;
		st.erase(st.begin());
		for(auto to : g[v]){
			if(res[to.F] < min(res[v], d[to.F])){
				st.erase({-res[to.F], to.F});
				res[to.F] = min(res[v], d[to.F]);
				st.insert({-res[to.F],to.F});
			}
		}
	}
	return res[_end];
}
set<pair<int,int>> st;
inline void go(){
	while(!st.empty()){
		int v = st.begin() -> S;
		st.erase(st.begin());
		for(auto to : g[v]){
			if(d[to.F] > d[v] + to.S){
				st.erase({d[to.F], to.F});
				st.insert({d[to.F]=d[v]+to.S,to.F});
			}
		}
	}
}
unordered_map<int,bool> used[N];
int main(){auto solve=[&](){

	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int x, y, w;
		cin >> x >> y >> w;
		g[x].pb({y, w});
		g[y].pb({x, w});
		used[x][y] = true;
		used[y][x] = true;
	}
	int k; cin >> k;
	int len = sqrt(k + .0);
	for(int i = 1, v; i <= k; ++i){
		cin >> v;
		st.insert({d[v]=0,v});
		if(i % len == 0 || i == n){
			go();
		}
	}
	int q; cin >> q;
	for(int s, e; q--;){
		cin >> s >> e;
		if(used[s].find(e) != used[s].end()){
			cout << min(d[s], d[e]) << '\n';
		}else{
			cout << get(s, e) << '\n';
		}
	}
};NFS;solve();}

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