oj.uz

Submission #1114366

# Submission time Handle Problem Language Result Execution time Memory
1114366 2024-11-18T17:00:01 Z raspy Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 374 ms 95532 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 2812 KB Output is correct
3 Correct 3 ms 8528 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 2896 KB Output is correct
8 Correct 2 ms 8528 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 2812 KB Output is correct
3 Correct 3 ms 8528 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 2896 KB Output is correct
8 Correct 2 ms 8528 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 4 ms 2896 KB Output is correct
12 Correct 5 ms 9040 KB Output is correct
13 Correct 4 ms 7248 KB Output is correct
14 Correct 2 ms 4556 KB Output is correct
15 Correct 3 ms 8660 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 2812 KB Output is correct
3 Correct 3 ms 8528 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 2896 KB Output is correct
8 Correct 2 ms 8528 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 4 ms 2896 KB Output is correct
12 Correct 5 ms 9040 KB Output is correct
13 Correct 4 ms 7248 KB Output is correct
14 Correct 2 ms 4556 KB Output is correct
15 Correct 3 ms 8660 KB Output is correct
16 Correct 316 ms 89020 KB Output is correct
17 Correct 57 ms 20036 KB Output is correct
18 Correct 84 ms 24136 KB Output is correct
19 Correct 374 ms 95532 KB Output is correct
20 Correct 205 ms 74424 KB Output is correct
21 Correct 25 ms 14160 KB Output is correct
22 Correct 240 ms 69292 KB Output is correct