Submission #378692

#	Time	Username	Problem	Language	Result	Execution time	Memory
378692		hhhhaura	Evacuation plan (IZhO18_plan)	C++14	0 / 100	270 ms	17024 KiB

plan

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
#define MAXN 1000005

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

using namespace std;
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {
	while(L < R) cerr << *L << " \n"[next(L) == R], ++ L;
}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {
	cerr << a << " ", kout(e...);
}
#else 
#define print(...) 0
#define vprint(...) 0
#endif
struct sb1 {
	struct edge {
		int to, cost;
	};
	int n, m, k;
	vector<vector<edge>> mp;
	vector<int> dis, g;
	void init_(int _n, int _m) {
		n = _n, m = _m;
		mp.assign(n + 1, vector<edge>());
		dis.assign(n + 1, INF);
		return;
	}
	void init1_(int _k) {
		k = _k;
		g.assign(k + 1, 0);
	}
	void build() {
		dis.assign(n + 1, INF);
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		rep(i, 1, k) {
			dis[g[i]] = 0;
			pq.push({0, g[i]});
 		}
 		while(pq.size()) {
 			pii p = pq.top(); pq.pop();
 			if(dis[p.second] != p.first) continue;
 			int cur = p.second;
 			for(auto i : mp[cur]) {
 				int v = i.cost + dis[cur];
 				if(dis[i.to] > v) {
 					dis[i.to] = v;
 					pq.push({v, i.to});
 				}
 			}
 		}
 		vprint(all(dis));
 		return;
	}
	int query(int s, int t) {
		return min(dis[s], dis[t]);
	}
	void add(int a, int b, int c) {
		mp[a].push_back({b, c});
		mp[b].push_back({a, c});
		return;
	}

} ;
struct sb2 {
	struct edge {
		int to, cost;
	};
	int n, m, k;
	vector<vector<edge>> mp;
	vector<int> dis, g, vis, dis1;
	void init_(int _n, int _m) {
		n = _n, m = _m;
		mp.assign(n + 1, vector<edge>());
		dis.assign(n + 1, INF);
		return;
	}
	void init1_(int _k) {
		k = _k;
		g.assign(k + 1, 0);
	}
	void build() {
		dis.assign(n + 1, INF);
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		rep(i, 1, k) {
			dis[g[i]] = 0;
			pq.push({0, g[i]});
 		}
 		while(pq.size()) {
 			pii p = pq.top(); pq.pop();
 			if(dis[p.second] != p.first) continue;
 			int cur = p.second;
 			for(auto i : mp[cur]) {
 				int v = i.cost + dis[cur];
 				if(dis[i.to] > v) {
 					dis[i.to] = v;
 					pq.push({v, i.to});
 				}
 			}
 		}
 		return;
	}
	int query(int s, int t) {
		dis1.assign(n + 1, INF);
		dis1[s] = 0;
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		pq.push({0, s});
 		while(pq.size()) {
 			pii p = pq.top(); pq.pop();
 			if(dis1[p.second] != p.first) continue;
 			int cur = p.second;
 			for(auto i : mp[cur]) {
 				int v = i.cost + dis1[cur];
 				if(dis1[i.to] > v) {
 					dis1[i.to] = v;
 					pq.push({v, i.to});
 				}
 			}
 		}
		return dfs(s, t);
	}
	void add(int a, int b, int c) {
		mp[a].push_back({b, c});
		mp[b].push_back({a, c});
		return;
	}
	int dfs(int s, int t) {
		if(s == t) return dis[s];
		int ans = INF;
		for(auto i : mp[s]) {
			if(i.cost + dis1[s] != dis1[i.to]) continue;
			int cur = dfs(i.to, t);
			if(cur != INF) ans = min({cur, dis[s], ans});
		}
		return ans;
	}

} ac;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m; cin >> n >> m;
	ac.init_(n, m);
	rep(i, 1, m) {
		int a, b, c;
		cin >> a >> b >> c;
		ac.add(a, b, c);
	}
	int k; cin >> k;
	ac.init1_(k);
	rep(i, 1, k) cin >> ac.g[i];
	ac.build();
	int q; cin >> q;
	rep(i, 1, q) {
		int s, t; cin >> s >> t;
		cout << ac.query(s, t) << "\n";
	}
	
	return 0;
}

Compilation message (stderr)

plan.cpp:4: warning: ignoring #pragma loop  [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
plan.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   24 | void vprint(auto L, auto R) {
      |             ^~~~
plan.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   24 | void vprint(auto L, auto R) {
      |                     ^~~~

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