Submission #209637

#	Time	Username	Problem	Language	Result	Execution time	Memory
209637		Kenzo_1114	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1354 ms	93432 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11