oj.uz

Submission #640559

# Submission time Handle Problem Language Result Execution time Memory
640559 2022-09-14T23:07:25 Z ymm Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 60856 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 set<pii> adj[N];
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]});
	}
	fill (dis, dis+N, inf);
	set<pii> s;
	Loop (i,0,k) {
		dis[p[i]] = 0;
		s.insert({0, p[i]});
	}
	Loop (_,0,n) {
		Loop (v,0,n) {
			if (dis[v] == 0)
				continue;
			int vc[2] = {inf, inf};
			for (auto [u, w] : A[v]) {
				if (vc[1] > dis[u] + w)
					vc[1] = dis[u] + w;
				if (vc[0] > vc[1])
					swap(vc[0], vc[1]);
			}
			dis[v] = vc[1];
		}
	}
	return dis[0];

	while (s.size()) {
		auto [d, v] = *s.begin();
		s.erase(s.begin());
		for (auto [u, w] : A[v]) {
			adj[u].insert({d + w, u});
			int d2 = adj[u].size() >= 2? (++adj[u].begin())->first: inf;
			if (d2 < dis[u]) {
				s.erase({dis[u], u});
				dis[u] = d2;
				s.insert({dis[u], u});
			}
		}
	}
	return dis[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7764 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 8 ms 7836 KB Output is correct
5 Correct 8 ms 7856 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 10 ms 7776 KB Output is correct
8 Correct 9 ms 7764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7764 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 8 ms 7836 KB Output is correct
5 Correct 8 ms 7856 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 10 ms 7776 KB Output is correct
8 Correct 9 ms 7764 KB Output is correct
9 Correct 8 ms 8016 KB Output is correct
10 Correct 5 ms 7668 KB Output is correct
11 Correct 8 ms 7764 KB Output is correct
12 Correct 13 ms 8144 KB Output is correct
13 Correct 10 ms 8276 KB Output is correct
14 Correct 5 ms 7764 KB Output is correct
15 Correct 7 ms 7764 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7764 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 8 ms 7836 KB Output is correct
5 Correct 8 ms 7856 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 10 ms 7776 KB Output is correct
8 Correct 9 ms 7764 KB Output is correct
9 Correct 8 ms 8016 KB Output is correct
10 Correct 5 ms 7668 KB Output is correct
11 Correct 8 ms 7764 KB Output is correct
12 Correct 13 ms 8144 KB Output is correct
13 Correct 10 ms 8276 KB Output is correct
14 Correct 5 ms 7764 KB Output is correct
15 Correct 7 ms 7764 KB Output is correct
16 Execution timed out 2071 ms 60856 KB Time limit exceeded
17 Halted 0 ms 0 KB -