oj.uz

Submission #169463

# Submission time Handle Problem Language Result Execution time Memory
169463 2019-12-20T14:06:05 Z Shafin666 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 996 ms 72820 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 2e5+10;
int dist[maxn], visited[maxn];
vector<pii> adj[maxn];
int E[maxn][2];

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

	for(int i = 0; i < N; i++) dist[i] = 1e9+7, E[i][0] = E[i][1] = 1e9+7;

	multiset<pii> s;
	for(int i = 0; i < K; i++) {
		s.insert({0, P[i]});
		E[P[i]][0] = E[P[i]][1] = 0;
		dist[P[i]] = 0;
	}

	while(!s.empty()) {
		pii p = *s.begin();
		s.erase(s.begin());

		int u = p.second;
		if(visited[u]) continue;
		visited[u] = 1;

		for(auto p : adj[u]) {
			int v = p.first, w = p.second;
			

			/*if(dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				s.insert({dist[v], v});
			}*/
			int d = dist[u] + w;
			if(d <= E[v][0]) {
				E[v][1] = E[v][0];
				E[v][0] = d;

				dist[v] = E[v][1];
				s.insert({E[v][1], v});
			}
			else if(d < E[v][1]) {
				E[v][1] = d;

				dist[v] = d;
				s.insert({d, v});
			}
		}
	}
  	return E[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 10 ms 5116 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 9 ms 5368 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 11 ms 5624 KB Output is correct
13 Correct 10 ms 5508 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5240 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 10 ms 5116 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 9 ms 5368 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 11 ms 5624 KB Output is correct
13 Correct 10 ms 5508 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5240 KB Output is correct
16 Correct 742 ms 63968 KB Output is correct
17 Correct 144 ms 21628 KB Output is correct
18 Correct 201 ms 22516 KB Output is correct
19 Correct 996 ms 72820 KB Output is correct
20 Correct 349 ms 52160 KB Output is correct
21 Correct 69 ms 11768 KB Output is correct
22 Correct 417 ms 50160 KB Output is correct