oj.uz

Submission #358627

# Submission time Handle Problem Language Result Execution time Memory
358627 2021-01-26T02:23:12 Z evn Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 822 ms 67420 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
typedef long long ll;
typedef pair<int, int> 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>;
int vis[100005];
int dist[100005];
vector<pii> adj[100005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i =0; i < M; i++){
		adj[R[i][0]].pb({R[i][1], L[i]});
		adj[R[i][1]].pb({R[i][0], L[i]});
	}
	for(int i = 0; i < N;i ++){
		dist[i] = 1e9;
	}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for(int i = 0; i < K; i++){
		dist[P[i]] = 0;
		pq.push({0, P[i]});
		vis[P[i]] = 1;
	}
	while(!pq.empty()){
		pii curr = pq.top(); pq.pop();
		int u = curr.s;
		if(vis[u] == 0){
			vis[u] = 1;
			continue;
		}
		if(vis[u] == 2)continue;
		vis[u] = 2;
		dist[u] = curr.f;
		for(pii edge : adj[u]){
			int next = edge.f;
			int weight = edge.s;
			if(vis[next] >= 2)continue;
			pq.push({weight+curr.f, next});
		}
	}
	return dist[0];

}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 5 ms 3052 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3360 KB Output is correct
13 Correct 7 ms 3436 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 5 ms 3052 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3360 KB Output is correct
13 Correct 7 ms 3436 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 750 ms 64448 KB Output is correct
17 Correct 83 ms 13804 KB Output is correct
18 Correct 111 ms 15212 KB Output is correct
19 Correct 822 ms 67420 KB Output is correct
20 Correct 493 ms 57816 KB Output is correct
21 Correct 44 ms 7660 KB Output is correct
22 Correct 455 ms 46572 KB Output is correct