oj.uz

Submission #527543

# Submission time Handle Problem Language Result Execution time Memory
527543 2022-02-17T15:22:19 Z Cantfindme Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 490 ms 73996 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
 
const ll maxn = 100010;
 
ll vis[maxn];
ll dist1[maxn], dist2[maxn];
vector <pi> adjlist[maxn];
ll n, e;
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N; e = M;
	
	for (ll i =0;i<e;i++) {
		ll a = R[i][0], b = R[i][1], c = L[i];
		adjlist[a].push_back(pi(b,c));
		adjlist[b].push_back(pi(a,c));
	}
	
	priority_queue <pi, vector<pi>, greater<pi>> pq;
	memset(dist1,-1,sizeof dist1);
	memset(dist2,-1,sizeof dist2);
	
	for (ll i =0;i<K;i++) {
		pq.push(pi(0, P[i]));
		dist1[P[i]] = dist2[P[i]] = 0;
	}
	
	while (!pq.empty()) {
		auto [d, x] = pq.top(); pq.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		
		for (auto [i, c]: adjlist[x]) {
			if (dist1[i] == -1) {
				dist1[i] = d + c;
			} else if (dist2[i] == -1) {
				dist2[i] = d + c;
				if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
				pq.push(pi(dist2[i], i));
			} else if (d + c < dist2[i]) {
				dist2[i] = d + c;
				if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
				pq.push(pi(dist2[i], i));
			}
		}
	}
	
	//for (int i =0;i<n;i++) {
		//cout << i << " " << dist1[i] << " " << dist2[i] << "\n";
	//}
	
	return dist2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 4 ms 4324 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 4 ms 4324 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct
9 Correct 4 ms 4556 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 3 ms 4356 KB Output is correct
12 Correct 6 ms 4940 KB Output is correct
13 Correct 5 ms 4944 KB Output is correct
14 Correct 3 ms 4220 KB Output is correct
15 Correct 3 ms 4300 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 4 ms 4324 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct
9 Correct 4 ms 4556 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 3 ms 4356 KB Output is correct
12 Correct 6 ms 4940 KB Output is correct
13 Correct 5 ms 4944 KB Output is correct
14 Correct 3 ms 4220 KB Output is correct
15 Correct 3 ms 4300 KB Output is correct
16 Correct 392 ms 68180 KB Output is correct
17 Correct 70 ms 15240 KB Output is correct
18 Correct 94 ms 17516 KB Output is correct
19 Correct 490 ms 73996 KB Output is correct
20 Correct 282 ms 56644 KB Output is correct
21 Correct 46 ms 9664 KB Output is correct
22 Correct 302 ms 51400 KB Output is correct