oj.uz

Submission #379864

# Submission time Handle Problem Language Result Execution time Memory
379864 2021-03-19T14:43:01 Z SavicS Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 469 ms 26088 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 100005;
const ll inf = 1e18 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m, s, t, a, b;

vector<pii> g[maxn];

ll dists[maxn];
ll distt[maxn];
ll dista[maxn];
ll distb[maxn];
void dij(int sv, ll dist[maxn]){
	ff(i,1,n)dist[i] = inf;
	priority_queue<pii,vector<pii>, greater<pii>> pq;
	pq.push({dist[sv] = 0, sv});
	while(!pq.empty()){
		pii v = pq.top(); pq.pop();
		if(dist[v.se] < v.fi)continue;
		for(auto c : g[v.se]){
			int u = c.fi;
			ll w = c.se;
			if(dist[u] > w + v.fi){
				dist[u] = w + v.fi;
				pq.push({dist[u], u});
			}
		}
	} 
}

ll rez = 0;

ll dp[maxn];
bool visited[maxn];
void dfs(int v, bool dir){
	visited[v] = 1;
	dp[v] = dista[v];
	for(auto c : g[v]){
		int u = c.fi;
		ll w = c.se;
		if(dir == 0){
			if(dists[v] + w + distt[u] == dists[t]){	
				if(!visited[u])dfs(u, dir);
				dp[v] = min(dp[v], dp[u]);
			}	
		}
		else{
			if(distt[v] + w + dists[u] == distt[s]){
				if(!visited[u])dfs(u, dir);
				dp[v] = min(dp[v], dp[u]);
			}	
		}
	}
	rez = min(rez, dp[v] + distb[v]);
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
	cin >> n >> m >> s >> t >> a >> b;
	ff(i,1,m){
		int u, v;
		ll w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	dij(s, dists);
	dij(t, distt);
	dij(a, dista);
	dij(b, distb);
	rez = dista[b];
	dfs(s, 0);
	ff(i,1,n)visited[i] = 0;
	dfs(t, 1);
	cout << rez << endl;
	return 0;
}
/**

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

// probati bojenje sahovski ili slicno

**/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 19520 KB Output is correct
2 Correct 375 ms 18168 KB Output is correct
3 Correct 469 ms 24096 KB Output is correct
4 Correct 412 ms 19356 KB Output is correct
5 Correct 415 ms 17980 KB Output is correct
6 Correct 360 ms 19568 KB Output is correct
7 Correct 435 ms 17948 KB Output is correct
8 Correct 438 ms 18016 KB Output is correct
9 Correct 367 ms 18024 KB Output is correct
10 Correct 358 ms 22280 KB Output is correct
11 Correct 223 ms 17260 KB Output is correct
12 Correct 457 ms 22260 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 19380 KB Output is correct
2 Correct 412 ms 19824 KB Output is correct
3 Correct 434 ms 19472 KB Output is correct
4 Correct 414 ms 19704 KB Output is correct
5 Correct 436 ms 20224 KB Output is correct
6 Correct 412 ms 21900 KB Output is correct
7 Correct 450 ms 22580 KB Output is correct
8 Correct 424 ms 19800 KB Output is correct
9 Correct 431 ms 20212 KB Output is correct
10 Correct 429 ms 19444 KB Output is correct
11 Correct 193 ms 16876 KB Output is correct
12 Correct 414 ms 26088 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4076 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 19 ms 6252 KB Output is correct
5 Correct 11 ms 4460 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 4 ms 2924 KB Output is correct
8 Correct 5 ms 3052 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 13 ms 4460 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct
12 Correct 2 ms 2796 KB Output is correct
13 Correct 3 ms 2796 KB Output is correct
14 Correct 3 ms 2796 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 19520 KB Output is correct
2 Correct 375 ms 18168 KB Output is correct
3 Correct 469 ms 24096 KB Output is correct
4 Correct 412 ms 19356 KB Output is correct
5 Correct 415 ms 17980 KB Output is correct
6 Correct 360 ms 19568 KB Output is correct
7 Correct 435 ms 17948 KB Output is correct
8 Correct 438 ms 18016 KB Output is correct
9 Correct 367 ms 18024 KB Output is correct
10 Correct 358 ms 22280 KB Output is correct
11 Correct 223 ms 17260 KB Output is correct
12 Correct 457 ms 22260 KB Output is correct
13 Correct 410 ms 19380 KB Output is correct
14 Correct 412 ms 19824 KB Output is correct
15 Correct 434 ms 19472 KB Output is correct
16 Correct 414 ms 19704 KB Output is correct
17 Correct 436 ms 20224 KB Output is correct
18 Correct 412 ms 21900 KB Output is correct
19 Correct 450 ms 22580 KB Output is correct
20 Correct 424 ms 19800 KB Output is correct
21 Correct 431 ms 20212 KB Output is correct
22 Correct 429 ms 19444 KB Output is correct
23 Correct 193 ms 16876 KB Output is correct
24 Correct 414 ms 26088 KB Output is correct
25 Correct 11 ms 4076 KB Output is correct
26 Correct 3 ms 2796 KB Output is correct
27 Correct 3 ms 2796 KB Output is correct
28 Correct 19 ms 6252 KB Output is correct
29 Correct 11 ms 4460 KB Output is correct
30 Correct 3 ms 2796 KB Output is correct
31 Correct 4 ms 2924 KB Output is correct
32 Correct 5 ms 3052 KB Output is correct
33 Correct 4 ms 3072 KB Output is correct
34 Correct 13 ms 4460 KB Output is correct
35 Correct 2 ms 2796 KB Output is correct
36 Correct 2 ms 2796 KB Output is correct
37 Correct 3 ms 2796 KB Output is correct
38 Correct 3 ms 2796 KB Output is correct
39 Correct 3 ms 2796 KB Output is correct
40 Correct 360 ms 23164 KB Output is correct
41 Correct 420 ms 22428 KB Output is correct
42 Correct 433 ms 22428 KB Output is correct
43 Correct 236 ms 18028 KB Output is correct
44 Correct 218 ms 18028 KB Output is correct
45 Correct 396 ms 21416 KB Output is correct
46 Correct 381 ms 20940 KB Output is correct
47 Correct 381 ms 23064 KB Output is correct
48 Correct 203 ms 14956 KB Output is correct
49 Correct 330 ms 22980 KB Output is correct
50 Correct 372 ms 21320 KB Output is correct
51 Correct 385 ms 21184 KB Output is correct