oj.uz

Submission #121104

# Submission time Handle Problem Language Result Execution time Memory
121104 2019-06-26T06:25:59 Z turbat Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 810 ms 57460 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

vector <pair <int , int> > edg[100005];
 
bool vis[100005][2];
long long dist[100005][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for (int i = 0;i < N;i++) 
		dist[i][0] = dist[i][1] = 2e9;
	for (int i = 0;i < M;i++) {
		edg[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		edg[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	priority_queue <pair <long long, int> > que;
	for (int i = 0;i < K;i++){
		que.push(make_pair(0, P[i]));
		vis[P[i]][0] = 1;
		dist[P[i]][0] = dist[P[i]][1] = 0;
	}
	while (!que.empty()){		
		int u = que.top().second;
		long long cost = -que.top().first;
		if (dist[u][1] > cost) dist[u][1] = cost;
		if (dist[u][0] > dist[u][1]) swap(dist[u][0], dist[u][1]);
		cost = dist[u][1];
		// if (vis[u][0]) cout << u<< ' '<< cost << endl;
		if (vis[u][0]){
			vis[u][1] = 1;
			for (auto v : edg[u])
				if (!vis[v.first][1] && dist[v.first][1] > cost + v.second){
					dist[v.first][1] = cost + v.second;
					if (dist[v.first][0] > dist[v.first][1]) swap(dist[v.first][0], dist[v.first][1]);
					que.push(make_pair(-dist[v.first][1], v.first));
				}
		}
		else vis[u][0] = 1;
		while (!que.empty() && vis[que.top().second][1])
			que.pop();
	}
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2944 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 7 ms 3140 KB Output is correct
13 Correct 8 ms 3200 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2944 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 7 ms 3140 KB Output is correct
13 Correct 8 ms 3200 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 585 ms 50040 KB Output is correct
17 Correct 110 ms 16880 KB Output is correct
18 Correct 141 ms 18544 KB Output is correct
19 Correct 810 ms 57460 KB Output is correct
20 Correct 302 ms 42328 KB Output is correct
21 Correct 49 ms 8568 KB Output is correct
22 Correct 333 ms 38392 KB Output is correct