oj.uz

Submission #209637

# Submission time Handle Problem Language Result Execution time Memory
209637 2020-03-15T00:53:13 Z Kenzo_1114 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1354 ms 93432 KB 
#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int MAXN = 1000010;
const int MAXM = 1000010;
const int INF = 2e9 + 7;

int N, M, R[MAXM][2], K, P[MAXN];
int L[MAXM]; 

int dist[MAXN], dist2[MAXN];
vector<int> graf[MAXN];
vector<int> cost[MAXN];

void DIK(int n)
{
	set<pair<pair<int, int>, int> > s;

	for(int i = 0; i < n; i++)
		s.insert({{dist2[i], dist[i]}, i});

	while(!s.empty())
	{
		int cur = s.begin()->second;
		s.erase(s.begin());

		for(int i = 0; i < graf[cur].size(); i++)
		{
			int adj = graf[cur][i];
			int c = cost[cur][i];
			int DIST = dist2[cur];

			if(dist[adj] > DIST + c)
			{
				s.erase({{dist2[adj], dist[adj]}, adj});
				dist2[adj] = dist[adj], dist[adj] = DIST + c;
				s.insert({{dist2[adj], dist[adj]}, adj});
			}
			else if(dist2[adj] > DIST + c)
			{
				s.erase({{dist2[adj], dist[adj]}, adj});
				dist2[adj] = DIST + c;
				s.insert({{dist2[adj], dist[adj]}, adj});
			}
		}
	}
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	for(int i = 0; i < m; i++)
	{
		int a = r[i][0];
		int b = r[i][1];

		graf[a].push_back(b);
		graf[b].push_back(a);
		cost[a].push_back(l[i]);
		cost[b].push_back(l[i]);
	}

	for(int i = 0; i < n; i++)
		dist[i] = dist2[i] = INF;

	for(int i = 0; i < k; i++)
		dist[p[i]] = dist2[p[i]] = 0;

	DIK(n);

	return dist2[0];
}
/*
int main ()
{
	scanf("%d %d", &N, &M);

	for(int i = 0; i < M; i++)	
		scanf("%d %d", &R[i][0], &R[i][1]);

	for(int i = 0; i < M; i++)	scanf("%d", &L[i]);

	scanf("%d", &K);

	for(int i = 0; i < K; i++)	scanf("%d", &P[i]);

	printf("%d\n", travel_plan(N, M, R, L, K, P));
}
*/

Compilation message

crocodile.cpp: In function 'void DIK(int)':
crocodile.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < graf[cur].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 29 ms 47352 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 34 ms 47480 KB Output is correct
5 Correct 32 ms 47480 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 31 ms 47480 KB Output is correct
8 Correct 31 ms 47480 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 29 ms 47352 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 34 ms 47480 KB Output is correct
5 Correct 32 ms 47480 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 31 ms 47480 KB Output is correct
8 Correct 31 ms 47480 KB Output is correct
9 Correct 38 ms 47480 KB Output is correct
10 Correct 32 ms 47224 KB Output is correct
11 Correct 34 ms 47352 KB Output is correct
12 Correct 35 ms 47608 KB Output is correct
13 Correct 33 ms 47736 KB Output is correct
14 Correct 31 ms 47356 KB Output is correct
15 Correct 31 ms 47352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 29 ms 47352 KB Output is correct
3 Correct 31 ms 47352 KB Output is correct
4 Correct 34 ms 47480 KB Output is correct
5 Correct 32 ms 47480 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 31 ms 47480 KB Output is correct
8 Correct 31 ms 47480 KB Output is correct
9 Correct 38 ms 47480 KB Output is correct
10 Correct 32 ms 47224 KB Output is correct
11 Correct 34 ms 47352 KB Output is correct
12 Correct 35 ms 47608 KB Output is correct
13 Correct 33 ms 47736 KB Output is correct
14 Correct 31 ms 47356 KB Output is correct
15 Correct 31 ms 47352 KB Output is correct
16 Correct 821 ms 85400 KB Output is correct
17 Correct 212 ms 62968 KB Output is correct
18 Correct 277 ms 64504 KB Output is correct
19 Correct 1354 ms 93432 KB Output is correct
20 Correct 382 ms 82044 KB Output is correct
21 Correct 105 ms 53240 KB Output is correct
22 Correct 464 ms 78840 KB Output is correct