oj.uz

Submission #402726

# Submission time Handle Problem Language Result Execution time Memory
402726 2021-05-12T09:52:06 Z Cantfindme Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 599 ms 73808 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 int maxn = 100010;

ll state[maxn];
ll dist[maxn], distreal[maxn];
vector <pi> adjlist[maxn];
int n, e;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N; e = M;
	
	for (int i =0;i<e;i++) {
		int 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(dist,-1,sizeof dist);
	memset(distreal,-1,sizeof distreal);
	
	for (int i =0;i<K;i++) {
		pq.push(pi(0, P[i]));
		distreal[P[i]] = 0;
		state[P[i]] = 2;
	}
	
	while (!pq.empty()) {
		auto [d,x] = pq.top(); pq.pop();
		if (d != distreal[x]) continue;
		
		
		for (auto [i,c] : adjlist[x]) {
			
			if (state[i] == 0) {
				state[i] = 1;
				dist[i] = c + d;
			} else if (state[i] == 1) {
				if (distreal[i] == -1 or distreal[i] > c + d) {
					distreal[i] = c + d;
					if (distreal[i] < dist[i]) swap(dist[i],distreal[i]);
										
					pq.push(pi(distreal[i],i));
				}
			}
		}
	}
	
	return distreal[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 3 ms 4336 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 4 ms 4300 KB Output is correct
9 Correct 5 ms 4556 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 7 ms 4764 KB Output is correct
13 Correct 7 ms 4940 KB Output is correct
14 Correct 3 ms 4172 KB Output is correct
15 Correct 4 ms 4300 KB Output is correct
16 Correct 491 ms 68080 KB Output is correct
17 Correct 79 ms 15160 KB Output is correct
18 Correct 105 ms 17440 KB Output is correct
19 Correct 599 ms 73808 KB Output is correct
20 Correct 327 ms 56516 KB Output is correct
21 Correct 41 ms 9644 KB Output is correct
22 Incorrect 367 ms 51272 KB Output isn't correct