oj.uz

Submission #71480

# Submission time Handle Problem Language Result Execution time Memory
71480 2018-08-24T21:19:55 Z FLDutchman Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 819 ms 53820 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define snd second
#define fst first
#define V vector
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int INF = 1e9 + 10;

struct edge{
	int v, l;
};

V<V<edge>> adj;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	adj.resize(N);
	FOR(i, 0, M) {
		adj[R[i][0]].pb({R[i][1], L[i]});
		adj[R[i][1]].pb({R[i][0], L[i]});
	}
	priority_queue<ii, vii, greater<ii>> q;
	vi dist(N, INF);
	vi vis(N, 0);
	FOR(i,0,K) {
		//dist[P[i]] = 0;
		vis[P[i]] = 1;
		q.push({0, P[i]});
	}
	while(!q.empty()){
		ii p = q.top(); q.pop();
		int u = p.snd, d = p.fst;
		//cout << u << " " << d << " " << vis[u] << endl;
		if(!vis[u]){
			vis[u] = 1;
			continue;
		}
		assert(dist[u] == INF || dist[u] <= d);
		if(dist[u] != INF) continue;
		dist[u] = d;
		if(u == 0) return d;
		for(edge e : adj[u]){
			int v = e.v, l = e.l;
			//cout<<v<<endl;
			if(dist[v] > d+l){
				//dist[v] = d+l;
				q.push({d+l, v});
			}
		}
	}
	return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 4 ms 692 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 4 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 3 ms 920 KB Output is correct
12 Correct 7 ms 1416 KB Output is correct
13 Correct 10 ms 1416 KB Output is correct
14 Correct 3 ms 1416 KB Output is correct
15 Correct 3 ms 1416 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 4 ms 692 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 4 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 3 ms 920 KB Output is correct
12 Correct 7 ms 1416 KB Output is correct
13 Correct 10 ms 1416 KB Output is correct
14 Correct 3 ms 1416 KB Output is correct
15 Correct 3 ms 1416 KB Output is correct
16 Correct 754 ms 49396 KB Output is correct
17 Correct 98 ms 49396 KB Output is correct
18 Correct 111 ms 49396 KB Output is correct
19 Correct 819 ms 53820 KB Output is correct
20 Correct 395 ms 53820 KB Output is correct
21 Correct 57 ms 53820 KB Output is correct
22 Correct 555 ms 53820 KB Output is correct