oj.uz

Submission #109144

# Submission time Handle Problem Language Result Execution time Memory
109144 2019-05-04T17:39:34 Z pamaj Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 845 ms 63496 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;

typedef pair<int, int> pii;

int vis[maxn], dist[maxn], dist2[maxn];
vector<pii> G[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(dist, 0x3f3f3f3f, sizeof(dist));
	memset(dist2, 0x3f3f3f3f, sizeof(dist));

	for(int i = 0; i < M; i++)
	{
		int a = R[i][0], b = R[i][1];

		G[a].push_back({L[i], b});
		G[b].push_back({L[i], a});
	}

	// for(int i = 0; i < N; i++)
	// 	for(auto u : G[i])
	// 		cout << i << " " << u.second << " " << u.first << "\n";

	priority_queue<pii, vector<pii>, greater<pii>> q;

	for(int i = 0; i < K; i++)
	{
		dist[P[i]] = dist2[P[i]] = 0;
		q.push({0, P[i]});
	}

	while(!q.empty())
	{
		auto a = q.top();
		q.pop();

		//cout << a.second << " \n";

		if(vis[a.second]) continue;
		vis[a.second] = true;

		for(auto u : G[a.second])
		{
			if(dist[u.second] > dist2[a.second] + u.first)
			{
				dist2[u.second] = dist[u.second];
				dist[u.second] = dist2[a.second] + u.first;

				// CÓDIGO MÁGICO COMEÇA AQUI
				if (dist2[u.second] != dist[u.second])
					q.push({dist2[u.second], u.second});
				// CÓDIGO MÁGICO TERMINA AQUI
			}
			else if(dist2[u.second] > dist2[a.second] + u.first)
			{
				dist2[u.second] = dist2[a.second] + u.first;
				q.push({dist2[u.second], u.second});
			}

		}
	}

	return dist2[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3312 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 6 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 6 ms 3584 KB Output is correct
8 Correct 6 ms 3584 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 7 ms 3584 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 8 ms 3968 KB Output is correct
14 Correct 5 ms 3584 KB Output is correct
15 Correct 6 ms 3584 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3312 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 6 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 6 ms 3584 KB Output is correct
8 Correct 6 ms 3584 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 7 ms 3584 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 8 ms 3968 KB Output is correct
14 Correct 5 ms 3584 KB Output is correct
15 Correct 6 ms 3584 KB Output is correct
16 Correct 737 ms 58940 KB Output is correct
17 Correct 123 ms 15300 KB Output is correct
18 Correct 159 ms 16744 KB Output is correct
19 Correct 845 ms 63496 KB Output is correct
20 Correct 357 ms 50308 KB Output is correct
21 Correct 65 ms 8696 KB Output is correct
22 Correct 346 ms 46972 KB Output is correct