Submission #1114366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114366		raspy	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	374 ms	95532 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

#define ll long long
#define inf 1'000'000'000'000
#define f first
#define s second
#define ii pair<ll, ll>

using namespace std;

vector<pair<ll, ll>> graf[100005];
ll dp[100005];
ii pv[100005];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
	for (int i = 0; i < m; i++)
	{
		graf[R[i][0]].push_back({R[i][1], L[i]});
		graf[R[i][1]].push_back({R[i][0], L[i]});
	}
	for (int i = 0; i < n; i++)
	{
		dp[i] = inf;
		pv[i] = {-1, -1};
	}
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for (int i = 0; i < k; i++)
	{
		pq.push({0, P[i]});
		dp[P[i]] = 0;
	}
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > dp[u]) continue;
		for (auto [v, w] : graf[u])
		{
			int td = d+w;
			if (pv[v].f == -1) pv[v].f = td;
			else if (td < pv[v].f) pv[v].s = pv[v].f, pv[v].f = td;
			else if (pv[v].s == -1) pv[v].s = td;
			else if (td < pv[v].s) pv[v].s = td;
			if (pv[v].s != -1 && pv[v].s < dp[v])
			{
				dp[v] = pv[v].s;
				pq.push({dp[v], v});
			}
		}
	}
	return dp[0];
}

// #define MAX_N 50000
// #define MAX_M 10000000

// static int N, M;
// static int R[MAX_M][2];
// static int L[MAX_M];
// static int K;
// static int P[MAX_N];
// static int solution;

// inline 
// void my_assert(int e) {if (!e) abort();}

// void read_input()
// {
//   int i;
//   my_assert(3==scanf("%d %d %d",&N,&M,&K));
//   for(i=0; i<M; i++)
//     my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
//   for(i=0; i<K; i++)
//     my_assert(1==scanf("%d",&P[i]));
//   my_assert(1==scanf("%d",&solution));
// }

// int main()
// {
//   int ans;
//   read_input();
//   ans = travel_plan(N,M,R,L,K,P);
//   if(ans==solution)
//     printf("Correct.\n");
//   else
//     printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

//   return 0;
// }

// // signed main()
// // {
// // 	return 0;
// // }

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11