oj.uz

Submission #209636

# Submission time Handle Problem Language Result Execution time Memory
209636 2020-03-15T00:51:45 Z Kenzo_1114 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2000 ms 47352 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];

			s.erase({{dist2[adj], dist[adj]}, adj});
			dist2[adj] = min(dist2[adj], dist2[cur] + c);
			if(dist2[adj] < dist[adj])	swap(dist[adj], dist2[adj]);
			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
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 47352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 47352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 47352 KB Time limit exceeded
2 Halted 0 ms 0 KB -