oj.uz

Submission #234915

# Submission time Handle Problem Language Result Execution time Memory
234915 2020-05-26T08:58:31 Z amoo_safar Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 602 ms 35716 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll dis[2][N];
vector<pll> G[N];

set<pll> st;

void Dij(int sc, int idx){
	memset(dis[idx], 31, sizeof dis[idx]);
	dis[idx][sc] = 0;
	st.insert({0, sc});
	int fr;
	while(!st.empty()){
		fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto ed : G[fr]){
			if(dis[idx][ed.F] > dis[idx][fr] + ed.S){
				st.erase({dis[idx][ed.F], ed.F});
				dis[idx][ed.F] = dis[idx][fr] + ed.S;
				st.insert({dis[idx][ed.F], ed.F});
			}
		}
	}
}

ll dp[N][4], d[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m;
	cin >> n >> m;
	ll s, t, l1, l2;
	cin >> s >> t >> l1 >> l2;
	ll u, v, w;
	for(int i = 0; i < m; i++){
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	Dij(l1, 0);
	Dij(l2, 1);
	memset(dp, 31, sizeof dp);
	memset(d, 31, sizeof d);
	for(int i = 0; i < 4; i++) dp[s][i] = (i & 1 ? dis[0][s] : 0) + (i & 2 ? dis[1][s] : 0);
	d[s] = 0;
	st.insert({d[s], s});
	int fr, adj;
	while(!st.empty()){
		fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto e : G[fr]){
			adj = e.F;
			if(d[adj] > d[fr] + e.S){
				st.erase({d[adj], adj});
				d[adj] = d[fr] + e.S;
				st.insert({d[adj], adj});
				memset(dp[adj], 31, sizeof dp[adj]);
			}
			if(d[adj] == d[fr] + e.S){
				for(int mk1 = 0; mk1 < 4; mk1 ++){
					for(int mk2 = 0; mk2 < 4; mk2 ++){
						if(mk1 & mk2) continue;
						dp[adj][mk1 | mk2] = min(dp[adj][mk1 | mk2], dp[fr][mk1] + (mk2 & 1 ? dis[0][adj] : 0) + (mk2 & 2 ? dis[1][adj] : 0));
					}
				}
			}
		}
	}

	cout << min(dis[0][l2], dp[t][3]) << '\n';
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 33148 KB Output is correct
2 Correct 495 ms 31900 KB Output is correct
3 Correct 439 ms 31992 KB Output is correct
4 Correct 465 ms 33272 KB Output is correct
5 Correct 406 ms 31736 KB Output is correct
6 Correct 497 ms 33272 KB Output is correct
7 Correct 401 ms 31608 KB Output is correct
8 Correct 415 ms 31944 KB Output is correct
9 Correct 418 ms 32784 KB Output is correct
10 Correct 328 ms 33016 KB Output is correct
11 Correct 147 ms 23288 KB Output is correct
12 Correct 492 ms 32504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 32508 KB Output is correct
2 Correct 526 ms 31608 KB Output is correct
3 Correct 491 ms 31736 KB Output is correct
4 Correct 527 ms 31608 KB Output is correct
5 Correct 521 ms 31736 KB Output is correct
6 Correct 475 ms 32120 KB Output is correct
7 Correct 494 ms 31480 KB Output is correct
8 Correct 512 ms 31784 KB Output is correct
9 Correct 491 ms 31736 KB Output is correct
10 Correct 511 ms 31608 KB Output is correct
11 Correct 180 ms 23344 KB Output is correct
12 Correct 440 ms 31968 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17920 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 14 ms 16128 KB Output is correct
4 Correct 30 ms 19328 KB Output is correct
5 Correct 22 ms 17792 KB Output is correct
6 Correct 14 ms 16128 KB Output is correct
7 Correct 14 ms 16128 KB Output is correct
8 Correct 16 ms 16256 KB Output is correct
9 Correct 14 ms 16128 KB Output is correct
10 Correct 21 ms 17664 KB Output is correct
11 Correct 13 ms 16000 KB Output is correct
12 Correct 13 ms 16000 KB Output is correct
13 Correct 14 ms 16000 KB Output is correct
14 Correct 15 ms 16128 KB Output is correct
15 Correct 14 ms 16128 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 33148 KB Output is correct
2 Correct 495 ms 31900 KB Output is correct
3 Correct 439 ms 31992 KB Output is correct
4 Correct 465 ms 33272 KB Output is correct
5 Correct 406 ms 31736 KB Output is correct
6 Correct 497 ms 33272 KB Output is correct
7 Correct 401 ms 31608 KB Output is correct
8 Correct 415 ms 31944 KB Output is correct
9 Correct 418 ms 32784 KB Output is correct
10 Correct 328 ms 33016 KB Output is correct
11 Correct 147 ms 23288 KB Output is correct
12 Correct 492 ms 32504 KB Output is correct
13 Correct 498 ms 32508 KB Output is correct
14 Correct 526 ms 31608 KB Output is correct
15 Correct 491 ms 31736 KB Output is correct
16 Correct 527 ms 31608 KB Output is correct
17 Correct 521 ms 31736 KB Output is correct
18 Correct 475 ms 32120 KB Output is correct
19 Correct 494 ms 31480 KB Output is correct
20 Correct 512 ms 31784 KB Output is correct
21 Correct 491 ms 31736 KB Output is correct
22 Correct 511 ms 31608 KB Output is correct
23 Correct 180 ms 23344 KB Output is correct
24 Correct 440 ms 31968 KB Output is correct
25 Correct 23 ms 17920 KB Output is correct
26 Correct 15 ms 16000 KB Output is correct
27 Correct 14 ms 16128 KB Output is correct
28 Correct 30 ms 19328 KB Output is correct
29 Correct 22 ms 17792 KB Output is correct
30 Correct 14 ms 16128 KB Output is correct
31 Correct 14 ms 16128 KB Output is correct
32 Correct 16 ms 16256 KB Output is correct
33 Correct 14 ms 16128 KB Output is correct
34 Correct 21 ms 17664 KB Output is correct
35 Correct 13 ms 16000 KB Output is correct
36 Correct 13 ms 16000 KB Output is correct
37 Correct 14 ms 16000 KB Output is correct
38 Correct 15 ms 16128 KB Output is correct
39 Correct 14 ms 16128 KB Output is correct
40 Correct 602 ms 35716 KB Output is correct
41 Correct 484 ms 33016 KB Output is correct
42 Correct 496 ms 32760 KB Output is correct
43 Correct 154 ms 23288 KB Output is correct
44 Correct 180 ms 23288 KB Output is correct
45 Correct 396 ms 31480 KB Output is correct
46 Correct 419 ms 31224 KB Output is correct
47 Correct 494 ms 33144 KB Output is correct
48 Correct 163 ms 22780 KB Output is correct
49 Correct 387 ms 35300 KB Output is correct
50 Correct 376 ms 31608 KB Output is correct
51 Correct 348 ms 31480 KB Output is correct