oj.uz

Submission #640560

# Submission time Handle Problem Language Result Execution time Memory
640560 2022-09-14T23:38:45 Z ymm Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 650 ms 59984 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 100'010;
static const int inf = 1e9;
static vector<pii> A[N];
static int vc[N][2];
static int dis[N];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	Loop (i,0,m) {
		A[r[i][0]].push_back({r[i][1], l[i]});
		A[r[i][1]].push_back({r[i][0], l[i]});
	}
	set<pii> s;
	fill (dis, dis+N, inf);
	Loop (i,0,N) vc[i][0] = vc[i][1] = inf;
	Loop (i,0,k) {
		dis[p[i]] = 0;
		s.insert({0, p[i]});
	}
	while (s.size()) {
		auto [d, v] = *s.begin();
		s.erase(s.begin());
		for (auto [u, w] : A[v]) {
			if (d + w < vc[u][1])
				vc[u][1] = d + w;
			if (vc[u][1] < vc[u][0])
				swap(vc[u][0], vc[u][1]);
			if (vc[u][1] < dis[u]) {
				s.erase({dis[u], u});
				dis[u] = vc[u][1];
				s.insert({dis[u], u});
			}
		}
	}
	return dis[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3828 KB Output is correct
7 Correct 3 ms 3924 KB Output is correct
8 Correct 3 ms 3924 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3828 KB Output is correct
7 Correct 3 ms 3924 KB Output is correct
8 Correct 3 ms 3924 KB Output is correct
9 Correct 3 ms 4052 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 3 ms 3956 KB Output is correct
12 Correct 5 ms 4308 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 2 ms 3796 KB Output is correct
15 Correct 3 ms 3924 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3828 KB Output is correct
7 Correct 3 ms 3924 KB Output is correct
8 Correct 3 ms 3924 KB Output is correct
9 Correct 3 ms 4052 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 3 ms 3956 KB Output is correct
12 Correct 5 ms 4308 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 2 ms 3796 KB Output is correct
15 Correct 3 ms 3924 KB Output is correct
16 Correct 434 ms 41120 KB Output is correct
17 Correct 65 ms 14116 KB Output is correct
18 Correct 83 ms 15536 KB Output is correct
19 Correct 650 ms 59984 KB Output is correct
20 Correct 241 ms 50644 KB Output is correct
21 Correct 34 ms 8524 KB Output is correct
22 Correct 288 ms 46868 KB Output is correct