oj.uz

Submission #235513

# Submission time Handle Problem Language Result Execution time Memory
235513 2020-05-28T11:54:12 Z ruler Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 861 ms 96708 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 5e5 + 5;

int DIS[6][N];
vector<pii> G[3][N];
set<pii> S;

void Dijkstra(int src, int g, int d[]) {
	d[src] = 0, S.insert(make_pair(0, src));
	while (!S.empty()) {
		int v = S.begin()->second; S.erase(S.begin());
		for (auto [u, w] : G[g][v]) if (d[v] + w < d[u]) {
			S.erase(make_pair(d[u], u));
			d[u] = d[v] + w;
			S.insert(make_pair(d[u], u));
		}
	}
}

int32_t main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n, m; cin >> n >> m;
	int s, t, l, r; cin >> s >> t >> l >> r;
	for (int i = 1; i <= m; i++) {
		int v, u, w; cin >> v >> u >> w;
		G[0][v].push_back(make_pair(u, w));
		G[0][u].push_back(make_pair(v, w));
	}
	memset(DIS, 63, sizeof DIS);
	Dijkstra(s, 0, DIS[0]);
	Dijkstra(t, 0, DIS[1]);
	Dijkstra(l, 0, DIS[2]);
	Dijkstra(r, 0, DIS[3]);
	for (int v = 1; v <= n; v++) {
		for (auto [u,w] : G[0][v]) if (DIS[0][v] + w == DIS[0][u] && DIS[0][v] + w + DIS[1][u] == DIS[0][t]) {
			G[1][v].push_back(make_pair(u, 0));
			G[2][u].push_back(make_pair(v, 0));
		}
		G[1][l].push_back(make_pair(v, DIS[2][v]));
		G[2][l].push_back(make_pair(v, DIS[2][v]));
		G[1][v].push_back(make_pair(r, DIS[3][v]));
		G[2][v].push_back(make_pair(r, DIS[3][v]));
	}
	int ans = INF;
	Dijkstra(l, 1, DIS[4]);
	ans = min(ans, DIS[4][r]);
	Dijkstra(l, 2, DIS[5]);
	ans = min(ans, DIS[5][r]);
	cout << ans << endl;

	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void Dijkstra(ll, ll, ll*)':
commuter_pass.cpp:32:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [u, w] : G[g][v]) if (d[v] + w < d[u]) {
             ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:58:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [u,w] : G[0][v]) if (DIS[0][v] + w == DIS[0][u] && DIS[0][v] + w + DIS[1][u] == DIS[0][t]) {
             ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 88420 KB Output is correct
2 Correct 695 ms 89196 KB Output is correct
3 Correct 739 ms 90716 KB Output is correct
4 Correct 765 ms 88276 KB Output is correct
5 Correct 715 ms 90332 KB Output is correct
6 Correct 813 ms 88284 KB Output is correct
7 Correct 716 ms 90480 KB Output is correct
8 Correct 731 ms 89808 KB Output is correct
9 Correct 737 ms 88948 KB Output is correct
10 Correct 549 ms 88832 KB Output is correct
11 Correct 365 ms 83028 KB Output is correct
12 Correct 698 ms 88740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 89080 KB Output is correct
2 Correct 790 ms 88936 KB Output is correct
3 Correct 762 ms 88764 KB Output is correct
4 Correct 771 ms 89032 KB Output is correct
5 Correct 812 ms 88992 KB Output is correct
6 Correct 751 ms 90212 KB Output is correct
7 Correct 767 ms 90124 KB Output is correct
8 Correct 806 ms 88848 KB Output is correct
9 Correct 815 ms 89244 KB Output is correct
10 Correct 792 ms 88696 KB Output is correct
11 Correct 441 ms 83936 KB Output is correct
12 Correct 861 ms 90232 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 61176 KB Output is correct
2 Correct 44 ms 59264 KB Output is correct
3 Correct 43 ms 59128 KB Output is correct
4 Correct 63 ms 62456 KB Output is correct
5 Correct 47 ms 61048 KB Output is correct
6 Correct 39 ms 59128 KB Output is correct
7 Correct 39 ms 59264 KB Output is correct
8 Correct 39 ms 59248 KB Output is correct
9 Correct 38 ms 59256 KB Output is correct
10 Correct 45 ms 60792 KB Output is correct
11 Correct 36 ms 59136 KB Output is correct
12 Correct 38 ms 59136 KB Output is correct
13 Correct 38 ms 59132 KB Output is correct
14 Correct 38 ms 59128 KB Output is correct
15 Correct 38 ms 59136 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 88420 KB Output is correct
2 Correct 695 ms 89196 KB Output is correct
3 Correct 739 ms 90716 KB Output is correct
4 Correct 765 ms 88276 KB Output is correct
5 Correct 715 ms 90332 KB Output is correct
6 Correct 813 ms 88284 KB Output is correct
7 Correct 716 ms 90480 KB Output is correct
8 Correct 731 ms 89808 KB Output is correct
9 Correct 737 ms 88948 KB Output is correct
10 Correct 549 ms 88832 KB Output is correct
11 Correct 365 ms 83028 KB Output is correct
12 Correct 698 ms 88740 KB Output is correct
13 Correct 802 ms 89080 KB Output is correct
14 Correct 790 ms 88936 KB Output is correct
15 Correct 762 ms 88764 KB Output is correct
16 Correct 771 ms 89032 KB Output is correct
17 Correct 812 ms 88992 KB Output is correct
18 Correct 751 ms 90212 KB Output is correct
19 Correct 767 ms 90124 KB Output is correct
20 Correct 806 ms 88848 KB Output is correct
21 Correct 815 ms 89244 KB Output is correct
22 Correct 792 ms 88696 KB Output is correct
23 Correct 441 ms 83936 KB Output is correct
24 Correct 861 ms 90232 KB Output is correct
25 Correct 51 ms 61176 KB Output is correct
26 Correct 44 ms 59264 KB Output is correct
27 Correct 43 ms 59128 KB Output is correct
28 Correct 63 ms 62456 KB Output is correct
29 Correct 47 ms 61048 KB Output is correct
30 Correct 39 ms 59128 KB Output is correct
31 Correct 39 ms 59264 KB Output is correct
32 Correct 39 ms 59248 KB Output is correct
33 Correct 38 ms 59256 KB Output is correct
34 Correct 45 ms 60792 KB Output is correct
35 Correct 36 ms 59136 KB Output is correct
36 Correct 38 ms 59136 KB Output is correct
37 Correct 38 ms 59132 KB Output is correct
38 Correct 38 ms 59128 KB Output is correct
39 Correct 38 ms 59136 KB Output is correct
40 Correct 814 ms 87920 KB Output is correct
41 Correct 722 ms 88572 KB Output is correct
42 Correct 749 ms 88736 KB Output is correct
43 Correct 462 ms 85724 KB Output is correct
44 Correct 417 ms 85716 KB Output is correct
45 Correct 771 ms 96708 KB Output is correct
46 Correct 761 ms 96144 KB Output is correct
47 Correct 777 ms 88360 KB Output is correct
48 Correct 424 ms 85076 KB Output is correct
49 Correct 633 ms 87664 KB Output is correct
50 Correct 748 ms 94236 KB Output is correct
51 Correct 729 ms 96652 KB Output is correct