oj.uz

Submission #547081

# Submission time Handle Problem Language Result Execution time Memory
547081 2022-04-09T12:43:02 Z Hanksburger Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 586 ms 93448 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > adj[100005];
priority_queue<pair<long long, long long> > pq;
long long dist[100005], dist2[100005];
bool visited[100005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (long long i=0; i<M; i++)
	{
		long long u=R[i][0], v=R[i][1], w=L[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (long long i=0; i<N; i++)
		dist[i]=dist2[i]=1e18;
	for (long long i=0; i<K; i++)
	{
		long long u=P[i];
		dist[u]=dist2[u]=0;
		pq.push({0, u});
	}
	while (!pq.empty())
	{
		long long u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (long long i=0; i<adj[u].size(); i++)
		{
			long long v=adj[u][i].first, w=adj[u][i].second;
			if (dist[v]>dist2[u]+w)
			{
				dist2[v]=dist[v];
				dist[v]=dist2[u]+w;
				pq.push({-dist2[v], v});
			}
			else if (dist2[v]>dist2[u]+w)
			{
				dist2[v]=dist2[u]+w;
				pq.push({-dist2[v], v});
			}
		}
	}
	return dist2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (long long i=0; i<adj[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2696 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 4 ms 3128 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 7 ms 3440 KB Output is correct
13 Correct 7 ms 3492 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2696 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 4 ms 3128 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 7 ms 3440 KB Output is correct
13 Correct 7 ms 3492 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 421 ms 85020 KB Output is correct
17 Correct 111 ms 19792 KB Output is correct
18 Correct 114 ms 22424 KB Output is correct
19 Correct 586 ms 93448 KB Output is correct
20 Correct 309 ms 68020 KB Output is correct
21 Correct 49 ms 10336 KB Output is correct
22 Correct 301 ms 64640 KB Output is correct