Submission #495047

#	Time	Username	Problem	Language	Result	Execution time	Memory
495047		Ierus	Evacuation plan (IZhO18_plan)	C++17	23 / 100	1078 ms	20052 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;
vector<pair<int,int>> g[N];
vector<int> d(N, INT_MAX);
void go(int v){
	set<pair<int,int>> st = {{d[v] = 0, v}};
	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});
			}
		}
	}
}
int main(){auto solve=[&](){
	int n, m;
	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});
	}
	int k; cin >> k;
	for(int i = 1, v; i <= k; ++i){
		cin >> v;
		go(v);
	}
	int q; cin >> q;
	for(int s, e; q--;){
		cin >> s >> e;
		cout << min(d[s], d[e]) << '\n';
	}
};NFS;solve();}

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