oj.uz

Submission #91452

# Submission time Handle Problem Language Result Execution time Memory
91452 2018-12-27T14:09:52 Z arman_ferdous Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 882 ms 78468 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;
const ll INF = 1e15;

int n, vis[N]; ll d[N][2];
vector< pair<int,ll> > g[N];
priority_queue< pair<ll,int>, vector< pair<ll,int> >, greater< pair<ll,int> > > q;

int travel_plan(int N_, int M, int R[][2], int L[], int K, int P[]) {
	n = N_;
	for(int i = 0; i < M; i++) {
		g[R[i][0]].push_back({R[i][1], L[i]});
		g[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i = 0; i < n; i++) d[i][0] = d[i][1] = INF;
	for(int i = 0; i < K; i++) {
		d[P[i]][0] = d[P[i]][1] = 0;
		q.push({0, P[i]});
	}
	while(!q.empty()) {
		auto top = q.top(); q.pop();
		int u = top.second; ll cw = top.first;
		if(vis[u]) continue; vis[u] = true;
		for(auto e : g[u]) {
			if(cw + e.second <= d[e.first][0]) {
				d[e.first][1] = d[e.first][0];
				d[e.first][0] = cw + e.second;
				q.push({d[e.first][1], e.first});
			}
			else if(cw + e.second < d[e.first][1]) {
				d[e.first][1] = cw + e.second;
				q.push({d[e.first][1], e.first});
			}
		}
	} return d[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(vis[u]) continue; vis[u] = true;
   ^~
crocodile.cpp:27:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(vis[u]) continue; vis[u] = true;
                        ^~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2832 KB Output is correct
3 Correct 3 ms 2832 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2912 KB Output is correct
6 Correct 4 ms 3104 KB Output is correct
7 Correct 4 ms 3104 KB Output is correct
8 Correct 4 ms 3104 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2832 KB Output is correct
3 Correct 3 ms 2832 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2912 KB Output is correct
6 Correct 4 ms 3104 KB Output is correct
7 Correct 4 ms 3104 KB Output is correct
8 Correct 4 ms 3104 KB Output is correct
9 Correct 6 ms 3432 KB Output is correct
10 Correct 3 ms 3432 KB Output is correct
11 Correct 5 ms 3432 KB Output is correct
12 Correct 7 ms 3860 KB Output is correct
13 Correct 7 ms 4080 KB Output is correct
14 Correct 4 ms 4080 KB Output is correct
15 Correct 5 ms 4080 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2832 KB Output is correct
3 Correct 3 ms 2832 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2912 KB Output is correct
6 Correct 4 ms 3104 KB Output is correct
7 Correct 4 ms 3104 KB Output is correct
8 Correct 4 ms 3104 KB Output is correct
9 Correct 6 ms 3432 KB Output is correct
10 Correct 3 ms 3432 KB Output is correct
11 Correct 5 ms 3432 KB Output is correct
12 Correct 7 ms 3860 KB Output is correct
13 Correct 7 ms 4080 KB Output is correct
14 Correct 4 ms 4080 KB Output is correct
15 Correct 5 ms 4080 KB Output is correct
16 Correct 598 ms 69560 KB Output is correct
17 Correct 107 ms 69560 KB Output is correct
18 Correct 146 ms 69560 KB Output is correct
19 Correct 882 ms 78468 KB Output is correct
20 Correct 323 ms 78468 KB Output is correct
21 Correct 50 ms 78468 KB Output is correct
22 Correct 357 ms 78468 KB Output is correct