oj.uz

Submission #230176

# Submission time Handle Problem Language Result Execution time Memory
230176 2020-05-08T22:56:13 Z MohamedAhmed04 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 750 ms 89424 KB 
//#include "grader.cpp"
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

pair<long long , long long> dist[MAX] ;
vector< vector< pair<int , long long> > >adj(MAX) ;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(dist , -1 , sizeof(dist)) ;
	for(int i = 0 ; i < M ; ++i)
	{
		int x = R[i][0] , y = R[i][1] ;
		adj[x].push_back({y , L[i]*1ll}) ;
		adj[y].push_back({x, L[i] * 1ll}) ;
	}
	priority_queue< pair<long long , int> , vector< pair<long long , int> > , greater< pair<long long , int> > >q ;
	for(int i = 0 ; i < K ; ++i)
	{
		dist[P[i]] = {0 , 0} ;
		q.push({0ll, P[i]}) ;
	}
	while(!q.empty())
	{
		pair<long long, int>p = q.top() ;
		q.pop() ;
		int node = p.second ;
		long long cost = p.first ;
		if(cost > dist[node].second)
			continue ;
		for(auto &child : adj[node])
		{
			int to = child.first ;
			long long ncost = cost + child.second ;
			long long prv = dist[to].second ;
			if(ncost < dist[to].first || dist[to].first == -1)
				dist[to].second = dist[to].first , dist[to].first = ncost ;
			else if(ncost < dist[to].second || dist[to].second == -1)
				dist[to].second = ncost ;
			if(dist[to].second < prv || (prv == -1 && dist[to].second != -1))
				q.push({dist[to].second, to}) ;
		}
	}
	return dist[0].second ;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 8 ms 4352 KB Output is correct
5 Correct 8 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 7 ms 4352 KB Output is correct
9 Correct 9 ms 4608 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 8 ms 4480 KB Output is correct
12 Correct 11 ms 4992 KB Output is correct
13 Correct 11 ms 5120 KB Output is correct
14 Correct 7 ms 4352 KB Output is correct
15 Correct 7 ms 4352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 8 ms 4352 KB Output is correct
5 Correct 8 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 7 ms 4352 KB Output is correct
9 Correct 9 ms 4608 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 8 ms 4480 KB Output is correct
12 Correct 11 ms 4992 KB Output is correct
13 Correct 11 ms 5120 KB Output is correct
14 Correct 7 ms 4352 KB Output is correct
15 Correct 7 ms 4352 KB Output is correct
16 Correct 611 ms 83456 KB Output is correct
17 Correct 99 ms 17632 KB Output is correct
18 Correct 126 ms 20092 KB Output is correct
19 Correct 750 ms 89424 KB Output is correct
20 Correct 391 ms 68856 KB Output is correct
21 Correct 50 ms 10876 KB Output is correct
22 Correct 412 ms 65276 KB Output is correct