oj.uz

Submission #157544

# Submission time Handle Problem Language Result Execution time Memory
157544 2019-10-12T10:12:49 Z GioChkhaidze Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1164 ms 98732 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int Nn=100005;
long long n,m,k,fix[Nn],D1[Nn],D2[Nn];
vector < pair < long long , long long > > v[Nn];
set < pair < long long , long long  > > st;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N,m=M,k=K;
	
	for (int i=0; i<m; i++) {
		v[R[i][0]].push_back({R[i][1],L[i]});
		v[R[i][1]].push_back({R[i][0],L[i]});
	}
	
	for (int i=0; i<n; i++)
		D1[i]=1e18,D2[i]=1e18;
	
	for (int i=0; i<k; i++) {
		D1[P[i]]=0,D2[P[i]]=0;
		st.insert({D2[P[i]],P[i]});
	}
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;
		
		for (int i=0; i<v[x].size(); i++) {
			int to=v[x][i].F,cost=v[x][i].S;
			if (D2[x]+cost<D1[to]) {
				D2[to]=D1[to];
				D1[to]=D2[x]+cost;
				st.insert({D2[to],to});
			}
				else 
			if (D2[x]+cost<D2[to]) {
				D2[to]=D2[x]+cost;
				st.insert({D2[to],to});
			}
		}
	}
	
	if (D2[0]==1e18) D2[0]=-1;
	return D2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2936 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 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 5 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2936 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3192 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 9 ms 3448 KB Output is correct
13 Correct 8 ms 3448 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 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 5 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2936 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3192 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 9 ms 3448 KB Output is correct
13 Correct 8 ms 3448 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 992 ms 86508 KB Output is correct
17 Correct 196 ms 24764 KB Output is correct
18 Correct 277 ms 26436 KB Output is correct
19 Correct 1164 ms 98732 KB Output is correct
20 Correct 414 ms 67704 KB Output is correct
21 Correct 74 ms 11984 KB Output is correct
22 Correct 481 ms 66248 KB Output is correct