oj.uz

Submission #749643

# Submission time Handle Problem Language Result Execution time Memory
749643 2023-05-28T10:39:11 Z happypotato Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 225664 KB 
#include "cyberland.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double
#pragma GCC optimize("Ofast")

const int mxN = 1e5 + 1;
vector<pii> adj[mxN];
short special[mxN];
int n, k, h;

bool cango[mxN];

void FindConnected() {
	queue<int> q;
	q.push(0); cango[0] = true;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		if (cur == h) continue;
		for (pii &v : adj[cur]) {
			if (!cango[v.ff]) {
				q.push(v.ff);
				cango[v.ff] = true;
			}
		}
	}
}

const int mxK = 70;
double dist[mxN][mxK];
priority_queue<pair<double, pii>, vector<pair<double, pii>>, greater<pair<double, pii>>> pq;
const double INF = 1e18, EPS = 1e-8;
void FindAnswer() {
	while (!pq.empty()) pq.pop();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= min(k, mxK - 1); j++) {
			dist[i][j] = INF;
		}
	}
	dist[0][0] = 0;
	pq.push({0, {0, 0}});
	for (int i = 0; i < n; i++) {
		if (cango[i] && special[i] == 0) {
			dist[i][0] = 0;
			pq.push({0, {i, 0}});
		}
	}
	while (!pq.empty()) {
		pair<double, pii> cur = pq.top();
		pq.pop();
		// if (cur.ss.ss <= 3) {
		// 	cerr << "DIJK " << cur.ff << ' ' << cur.ss.ff << ' ' << cur.ss.ss << endl;
		// }
		if (cur.ff > dist[cur.ss.ff][cur.ss.ss]) continue;
		if (cur.ss.ff == h) continue;
		double ncur;
		for (pii &v : adj[cur.ss.ff]) {
			ncur = cur.ff + v.ss;
			if (ncur < dist[v.ff][cur.ss.ss]) {
				dist[v.ff][cur.ss.ss] = ncur;
				pq.push({ncur, {v.ff, cur.ss.ss}});
			}
			if (special[v.ff] == 2 && cur.ss.ss + 1 < mxK) {
				ncur /= 2;
				if (ncur < dist[v.ff][cur.ss.ss + 1]) {
					dist[v.ff][cur.ss.ss + 1] = ncur;
					pq.push({ncur, {v.ff, cur.ss.ss + 1}});
				}
			}
		}
	}
}

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr) {
	n = N; k = K; h = H;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		cango[i] = false;
	}
	for (int i = 0; i < M; i++) {
		adj[X[i]].pb({Y[i], C[i]});
		adj[Y[i]].pb({X[i], C[i]});
	}
	for (int i = 0; i < n; i++) {
		special[i] = arr[i];
	}
	// assert(special[0] == 1 && special[h] == 1);

	FindConnected();
	if (!cango[h]) return -1;

	// cerr << setprecision(1) << fixed;
	FindAnswer();
	// cerr << "DEBUG:\n";
	// for (int i = 0; i < n; i++) {
	// 	cerr << "NODE " << i << ": ";
	// 	for (int j = 0; j < 3; j++) cerr << dist[i][j] << ' ';
	// 	cerr << endl;
	// }
	double res = 1e18;
	for (int i = 0; i <= min(k, mxK - 1); i++) {
		res = min(res, dist[h][i]);
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2800 KB Correct.
2 Correct 22 ms 2768 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3340 KB Correct.
2 Correct 26 ms 3428 KB Correct.
3 Correct 25 ms 3412 KB Correct.
4 Correct 26 ms 3368 KB Correct.
5 Correct 26 ms 3356 KB Correct.
6 Correct 26 ms 8980 KB Correct.
7 Correct 32 ms 8788 KB Correct.
8 Correct 20 ms 15188 KB Correct.
9 Correct 23 ms 2772 KB Correct.
10 Correct 23 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3284 KB Correct.
2 Correct 27 ms 3412 KB Correct.
3 Correct 24 ms 3412 KB Correct.
4 Correct 26 ms 2796 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 9 ms 8020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 45540 KB Correct.
2 Correct 316 ms 3728 KB Correct.
3 Correct 276 ms 3752 KB Correct.
4 Correct 304 ms 3556 KB Correct.
5 Correct 245 ms 2884 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3412 KB Correct.
2 Correct 23 ms 3392 KB Correct.
3 Correct 25 ms 3412 KB Correct.
4 Correct 27 ms 9384 KB Correct.
5 Correct 19 ms 2792 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3440 KB Correct.
2 Correct 20 ms 3504 KB Correct.
3 Correct 47 ms 9292 KB Correct.
4 Correct 18 ms 6868 KB Correct.
5 Correct 21 ms 2788 KB Correct.
6 Correct 21 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 4052 KB Correct.
2 Correct 45 ms 4944 KB Correct.
3 Correct 714 ms 66032 KB Correct.
4 Correct 635 ms 17388 KB Correct.
5 Correct 1262 ms 77912 KB Correct.
6 Correct 594 ms 63372 KB Correct.
7 Correct 626 ms 18656 KB Correct.
8 Correct 665 ms 5196 KB Correct.
9 Correct 239 ms 4932 KB Correct.
10 Correct 226 ms 4132 KB Correct.
11 Correct 669 ms 3816 KB Correct.
12 Correct 268 ms 4128 KB Correct.
13 Correct 290 ms 4128 KB Correct.
14 Correct 489 ms 33596 KB Correct.
15 Correct 655 ms 11128 KB Correct.
16 Correct 267 ms 4092 KB Correct.
17 Correct 316 ms 4180 KB Correct.
18 Correct 278 ms 3980 KB Correct.
19 Correct 641 ms 4184 KB Correct.
20 Correct 21 ms 3260 KB Correct.
21 Correct 20 ms 3356 KB Correct.
22 Correct 40 ms 7024 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 6288 KB Correct.
2 Correct 146 ms 9596 KB Correct.
3 Correct 694 ms 65672 KB Correct.
4 Correct 1608 ms 8352 KB Correct.
5 Execution timed out 3070 ms 225664 KB Time limit exceeded
6 Halted 0 ms 0 KB -