oj.uz

Submission #402706

# Submission time Handle Problem Language Result Execution time Memory
402706 2021-05-12T09:20:44 Z Antekb Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 817 ms 61560 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp(x, y) make_pair(x ,y)
typedef long long ll;
const ll INF=1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	ll dist[N], dist2[N];
	vector<pair<int, int> > E[N];
	for(int i=0; i<M; i++){
		E[R[i][0]].push_back(mp(R[i][1], L[i]));
		E[R[i][1]].push_back(mp(R[i][0], L[i]));
	}
	for(int i=0; i<N;i++)dist[i]=dist2[i]=INF;
	for(int i=0; i<K; i++)dist[P[i]]=dist2[P[i]]=0;
	set<pair<ll, int> > S;
	for(int i=0;i<N; i++){
		S.insert(mp(dist[i], i));
	}
	while(S.size()){
		int v=(*S.begin()).nd;
		S.erase(S.begin());
		if(v==0){
			return dist[v];
		}
		for(auto i:E[v]){
			if(dist[v]+i.nd<dist[i.st]){
				S.erase(S.find(mp(dist[i.st], i.st)));
				if(dist[v]+i.nd>dist2[i.st])dist[i.st]=dist[v]+i.nd;
				else{
					dist[i.st]=dist2[i.st];
					dist2[i.st]=dist[v]+i.nd;
				}
				S.insert(mp(dist[i.st], i.st));
			}
		}
	}
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 444 KB Output is correct
12 Correct 4 ms 696 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 444 KB Output is correct
12 Correct 4 ms 696 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 582 ms 52816 KB Output is correct
17 Correct 146 ms 20756 KB Output is correct
18 Correct 157 ms 22292 KB Output is correct
19 Correct 817 ms 61560 KB Output is correct
20 Correct 315 ms 47192 KB Output is correct
21 Correct 63 ms 8096 KB Output is correct
22 Correct 369 ms 46348 KB Output is correct