oj.uz

Submission #672553

# Submission time Handle Problem Language Result Execution time Memory
672553 2022-12-16T15:25:25 Z mmk Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 990 ms 86896 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;
const ll MAXN = 1e5+10;
ll Dist1[MAXN], Dist2[MAXN];
bool marc[MAXN];
vector<ll> grafo[MAXN];
vector<ll> weight[MAXN];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for(ll i = 0; i < m; i++)
	{
		ll a = R[i][0];
		ll b = R[i][1];
		grafo[a].push_back(b);
		grafo[b].push_back(a);
		weight[a].push_back(L[i]);
		weight[b].push_back(L[i]);
	}
	
	set<pair<ll,ll>> s;
	for(ll i = 0; i < n; i++)
	{
		Dist1[i] = INF;
		Dist2[i] = INF;
	}
	for(ll i = 0; i < K; i++)
	{
		Dist1[P[i]] = 0;
		Dist2[P[i]] = 0;
		s.emplace(0,P[i]);
	}
	while(!s.empty())
	{
		ll cur = s.begin()->second;
		s.erase(s.begin());
		if(marc[cur]) continue;
		marc[cur] = true;
		for(ll i = 0; i < grafo[cur].size(); i++)
		{
			ll viz = grafo[cur][i];
			ll p = weight[cur][i];
			if(Dist2[cur] + p < Dist1[viz])
			{
				Dist2[viz] = Dist1[viz];
				Dist1[viz] = Dist2[cur] + p;
				s.emplace(Dist2[viz],viz);
			}
			else if(Dist2[cur] + p < Dist2[viz])
			{
				Dist2[viz] = Dist2[cur] + p;
				s.emplace(Dist2[viz],viz);
			}
		}
	}
	return Dist2[0];
}

Compilation message

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

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 6 ms 5588 KB Output is correct
13 Correct 5 ms 5716 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5128 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 6 ms 5588 KB Output is correct
13 Correct 5 ms 5716 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5128 KB Output is correct
16 Correct 698 ms 73808 KB Output is correct
17 Correct 113 ms 24628 KB Output is correct
18 Correct 154 ms 26092 KB Output is correct
19 Correct 990 ms 86896 KB Output is correct
20 Correct 268 ms 60612 KB Output is correct
21 Correct 70 ms 13056 KB Output is correct
22 Correct 314 ms 54648 KB Output is correct