oj.uz

Submission #944002

# Submission time Handle Problem Language Result Execution time Memory
944002 2024-03-12T06:28:19 Z Amaarsaa Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 402 ms 75420 KB 
#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
const ll INF = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	ll i, x, c, y, s, p, X;
	vector < pair < ll,ll > > adj[N + 2];
	
	for (i = 0; i < M; i ++) {
		x = R[i][0];
		y = R[i][1];
		adj[x].push_back({y, L[i]});
		adj[y].push_back({x, L[i]});
	}
	priority_queue < pll, vector < pll > , greater < pll > > pq;
	ll D[N + 2][3];
	for (i = 0; i < N; i ++) D[i][1] = INF, D[i][0] = INF;
	for (i = 0; i < K; i ++) {
		pq.push({0, P[i]});
		D[P[i]][0] = D[P[i]][1] = 0;
	}
	
	while(!pq.empty()) {
		x = pq.top().second;
		c = pq.top().first;
		pq.pop();
		if ( D[x][1] != c) continue;
		
		for ( pair < ll, ll > pa : adj[x]) {
			X = pa.first;
			s = pa.second;
			p = D[X][1];
			if ( s + c < D[X][0]) {
				if ( D[X][1] != D[X][0]) {
					D[X][1]= D[X][0];
					pq.push({D[X][1], X});
				}
				D[X][0] = s + c;
			}
			else {
				if ( s + c< D[X][1]) {
					D[X][1] = s + c;
					pq.push({D[X][1], X});
				}
			}
		}
	}
  	return D[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:11:20: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   11 |  ll i, x, c, y, s, p, X;
      |                    ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4540 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5052 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4540 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5052 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 329 ms 66348 KB Output is correct
17 Correct 55 ms 16808 KB Output is correct
18 Correct 77 ms 19028 KB Output is correct
19 Correct 402 ms 75420 KB Output is correct
20 Correct 235 ms 53336 KB Output is correct
21 Correct 28 ms 9908 KB Output is correct
22 Correct 252 ms 50260 KB Output is correct