oj.uz

Submission #330873

# Submission time Handle Problem Language Result Execution time Memory
330873 2020-11-26T19:31:23 Z evn Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 362 ms 31964 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> pii;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
vector<pii> adj[100005];
set<int> parents[100005];
ll dijkstra[100005];
ll dijkstra2[100005];
bool vis[100005];
signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M, S, T, U, V;
	cin >> N >> M >> S >> T >> U >> V; S--; T--; U--; V--;
	for(int i = 0; i < M;i ++){
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	//run yikstras once
	for(int i =0; i < N;i ++){
		dijkstra[i] = 1e18;
		dijkstra2[i] = 1e18;
	}
	dijkstra[S] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq; 
	pq.push({0,S});
	while(!pq.empty()){
		pii curr = pq.top(); pq.pop();
		if(dijkstra[curr.s] != curr.f)continue; 
		for(auto it : adj[curr.s]){
			ll next = it.f;
			ll weight = it.s;
			if(weight + dijkstra[curr.s] == dijkstra[next]){
				parents[next].insert(curr.s);
			}
			if(weight + dijkstra[curr.s] < dijkstra[next]){
				parents[next].clear();
				parents[next].insert(curr.s);
				dijkstra[next] = weight + dijkstra[curr.s];
				pq.push({dijkstra[next], next});
			}
		}
	}
	queue<int> q;
	q.push(T);
	while(!q.empty()){
		int top = q.front(); q.pop();
		for(int u : parents[top]){
			if(!vis[u]){
				adj[u].pb({top,0});
				adj[top].pb({u,0});
				vis[u] = true;
				q.push(u);
			}
		}
	}
	dijkstra2[U] = 0;
	pq.push({0, U});
	while(!pq.empty()){
		pii curr = pq.top(); pq.pop();
		if(dijkstra2[curr.s] != curr.f)continue;
		for(auto it : adj[curr.s]){
			ll next = it.f;
			ll weight = it.s;
			if(weight + dijkstra2[curr.s] < dijkstra2[next]){
				//cout << curr.s << " " << next << " " << weight << '\n';
				dijkstra2[next] = weight+dijkstra2[curr.s];
				pq.push({dijkstra2[next], next});
			}
		}
	}
	cout << dijkstra2[V] << '\n';




}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 25564 KB Output is correct
2 Correct 336 ms 28640 KB Output is correct
3 Correct 336 ms 29920 KB Output is correct
4 Correct 313 ms 27492 KB Output is correct
5 Correct 352 ms 31840 KB Output is correct
6 Correct 294 ms 24676 KB Output is correct
7 Correct 347 ms 30568 KB Output is correct
8 Correct 342 ms 30176 KB Output is correct
9 Correct 282 ms 24160 KB Output is correct
10 Correct 253 ms 24544 KB Output is correct
11 Correct 156 ms 21988 KB Output is correct
12 Correct 312 ms 24288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 27488 KB Output is correct
2 Correct 337 ms 27876 KB Output is correct
3 Correct 326 ms 27492 KB Output is correct
4 Correct 335 ms 27624 KB Output is correct
5 Correct 341 ms 28132 KB Output is correct
6 Correct 337 ms 29664 KB Output is correct
7 Correct 362 ms 31964 KB Output is correct
8 Correct 328 ms 27876 KB Output is correct
9 Correct 330 ms 28256 KB Output is correct
10 Correct 315 ms 27488 KB Output is correct
11 Correct 172 ms 22884 KB Output is correct
12 Correct 331 ms 29664 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9196 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Incorrect 5 ms 7404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 25564 KB Output is correct
2 Correct 336 ms 28640 KB Output is correct
3 Correct 336 ms 29920 KB Output is correct
4 Correct 313 ms 27492 KB Output is correct
5 Correct 352 ms 31840 KB Output is correct
6 Correct 294 ms 24676 KB Output is correct
7 Correct 347 ms 30568 KB Output is correct
8 Correct 342 ms 30176 KB Output is correct
9 Correct 282 ms 24160 KB Output is correct
10 Correct 253 ms 24544 KB Output is correct
11 Correct 156 ms 21988 KB Output is correct
12 Correct 312 ms 24288 KB Output is correct
13 Correct 324 ms 27488 KB Output is correct
14 Correct 337 ms 27876 KB Output is correct
15 Correct 326 ms 27492 KB Output is correct
16 Correct 335 ms 27624 KB Output is correct
17 Correct 341 ms 28132 KB Output is correct
18 Correct 337 ms 29664 KB Output is correct
19 Correct 362 ms 31964 KB Output is correct
20 Correct 328 ms 27876 KB Output is correct
21 Correct 330 ms 28256 KB Output is correct
22 Correct 315 ms 27488 KB Output is correct
23 Correct 172 ms 22884 KB Output is correct
24 Correct 331 ms 29664 KB Output is correct
25 Correct 14 ms 9196 KB Output is correct
26 Correct 5 ms 7404 KB Output is correct
27 Incorrect 5 ms 7404 KB Output isn't correct
28 Halted 0 ms 0 KB -