oj.uz

Submission #117591

# Submission time Handle Problem Language Result Execution time Memory
117591 2019-06-16T17:59:40 Z KieranHorgan Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 745 ms 84580 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())

vector<pair<int,int>> AdjList[1000005];
int dist1[100005];
int dist2[100005];

// signed main() {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(NULL);
// 	long long seed;
// 	asm("rdtsc" : "=A"(seed));
// 	srand(seed);

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i = 0; i < M; i++) {
		AdjList[R[i][0]].push_back({L[i], R[i][1]});
		AdjList[R[i][1]].push_back({L[i], R[i][0]});
	}

	// int n, m, k;
	// cin >> n >> m >> k;
	// for(int i = 0; i < m; i++) {
		// int u, v, w;
		// cin >> u >> v >> w;
		// AdjList[u].push_back({w,v});
		// AdjList[v].push_back({w,u});
	// }
	// vector<int> destination(k);
	// for(auto &x: destination)
		// cin >> x;
	int n=N;
	int m=M;
	int k=K;
	vector<int> destination;
	for(int i = 0; i < k; i++)
		destination.push_back(P[i]);

	memset(dist1, 63, sizeof(dist1));
	memset(dist2, 63, sizeof(dist2));
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	for(auto x: destination) {
		pq.push({0,x});
		dist1[x]=0;
		dist2[x]=0;
	}
	while(!pq.empty()) {
		int u = pq.top().second;
		int w = pq.top().first; pq.pop();
		if(w > dist2[u]) continue;
		// cerr << u << ": " << dist2[u] << endl;
		for(auto v: AdjList[u])
			if(dist2[u]+v.first < dist1[v.second]) {
				// cerr << " " << u << "->" << v.second << endl;
				dist2[v.second] = dist1[v.second];
				dist1[v.second] = dist2[u] + v.first;
				if(dist2[v.second])
					pq.push({dist2[v.second], v.second});
			} else if(dist2[u]+v.first < dist2[v.second]) {
				// cerr << "  " << u << "->" << v.second << endl;
				dist2[v.second] = dist2[u] + v.first;
				pq.push({dist2[v.second], v.second});
			}
	}

	// cout << dist2[0] << endl;
	return dist2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:40:6: warning: unused variable 'n' [-Wunused-variable]
  int n=N;
      ^
crocodile.cpp:41:6: warning: unused variable 'm' [-Wunused-variable]
  int m=M;
      ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24576 KB Output is correct
2 Correct 21 ms 24576 KB Output is correct
3 Correct 21 ms 24568 KB Output is correct
4 Correct 23 ms 24704 KB Output is correct
5 Correct 22 ms 24704 KB Output is correct
6 Correct 22 ms 24744 KB Output is correct
7 Correct 22 ms 24676 KB Output is correct
8 Correct 22 ms 24704 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24576 KB Output is correct
2 Correct 21 ms 24576 KB Output is correct
3 Correct 21 ms 24568 KB Output is correct
4 Correct 23 ms 24704 KB Output is correct
5 Correct 22 ms 24704 KB Output is correct
6 Correct 22 ms 24744 KB Output is correct
7 Correct 22 ms 24676 KB Output is correct
8 Correct 22 ms 24704 KB Output is correct
9 Correct 23 ms 24960 KB Output is correct
10 Correct 21 ms 24568 KB Output is correct
11 Correct 22 ms 24704 KB Output is correct
12 Correct 25 ms 25088 KB Output is correct
13 Correct 24 ms 25088 KB Output is correct
14 Correct 22 ms 24696 KB Output is correct
15 Correct 23 ms 24696 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24576 KB Output is correct
2 Correct 21 ms 24576 KB Output is correct
3 Correct 21 ms 24568 KB Output is correct
4 Correct 23 ms 24704 KB Output is correct
5 Correct 22 ms 24704 KB Output is correct
6 Correct 22 ms 24744 KB Output is correct
7 Correct 22 ms 24676 KB Output is correct
8 Correct 22 ms 24704 KB Output is correct
9 Correct 23 ms 24960 KB Output is correct
10 Correct 21 ms 24568 KB Output is correct
11 Correct 22 ms 24704 KB Output is correct
12 Correct 25 ms 25088 KB Output is correct
13 Correct 24 ms 25088 KB Output is correct
14 Correct 22 ms 24696 KB Output is correct
15 Correct 23 ms 24696 KB Output is correct
16 Correct 570 ms 79756 KB Output is correct
17 Correct 121 ms 36184 KB Output is correct
18 Correct 152 ms 37740 KB Output is correct
19 Correct 745 ms 84580 KB Output is correct
20 Correct 319 ms 71672 KB Output is correct
21 Correct 67 ms 29872 KB Output is correct
22 Incorrect 369 ms 68108 KB Output isn't correct