oj.uz

Submission #804411

# Submission time Handle Problem Language Result Execution time Memory
804411 2023-08-03T08:34:21 Z MadokaMagicaFan Cyberland (APIO23_cyberland) C++17
15 / 100
 3000 ms 10580 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;
vector<array<ll, 2>> adj[N];
bitset<N> v;
ll mind1[N];
ll mind2[N];
ll sme[N];
ll inf = 1e18;

double
solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
	for (int i = 0; i < n; ++i) {
		sme[i] = inf;
		mind2[i] = inf;
		mind1[i] = 0;
		while (sz(adj[i]))
			adj[i].pop_back();
	}
	v = 0;

	if (h == 0) return 0;
	for (int i = 0; i < m; ++i) {
		adj[x[i]].pb({y[i], c[i]});
		if (y[i] != h)
			sme[x[i]] = min(sme[x[i]], (ll)c[i]);
		adj[y[i]].pb({x[i], c[i]});
		if (x[i] != h)
			sme[y[i]] = min(sme[y[i]], (ll)c[i]);
	}

	priority_queue<array<ll, 2>> q;
	for (int i = 1; i < n; ++i) {
		if (arr[i] == 0) {
			q.push({0, i});
			mind1[i] = 0;
		}
		else
			mind1[i] = inf;
	}
	q.push({0, 0});

	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		if (u[1] == h) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind1[u[1]]+ x[1] < mind1[x[0]]) {
				mind1[x[0]] = mind1[u[1]]+ x[1];
				q.push({-mind1[x[0]], x[0]});
			}
		}
	}

	if (mind1[h] > 1e17) return -1;

	long double ans = mind1[h];
	while (sz(q)) q.pop();
	mind2[h] = 0;
	q.push({0, h});

	v = 0;
	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind2[u[1]]+ x[1] < mind2[x[0]]) {
				mind2[x[0]] = mind2[u[1]]+ x[1];
				q.push({-mind2[x[0]], x[0]});
			}
		}
	}

	for (int i = 1; i < n; ++i) {
		if (mind1[i] > 1e17) continue;
		if (arr[i] != 2) continue;
		long double v = mind1[i];
		long double z = sme[i];
		v = v / ((ld)2);
		int c = min(k-1, 100);
		if (sme[i] >= 1e17) c = 0;
		while (c && z * ((ld) 2) <= v) {
			v = v / ((ld) 2) + z;
		}

		z = mind2[i];
		ans = min(ans, z + v);
	}


	return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3028 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3748 KB Correct.
2 Correct 25 ms 3924 KB Correct.
3 Correct 24 ms 3844 KB Correct.
4 Correct 25 ms 4016 KB Correct.
5 Correct 24 ms 3876 KB Correct.
6 Correct 24 ms 4704 KB Correct.
7 Correct 28 ms 5004 KB Correct.
8 Correct 13 ms 5252 KB Correct.
9 Correct 24 ms 3648 KB Correct.
10 Correct 22 ms 3636 KB Correct.

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3868 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 10580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3880 KB Correct.
2 Correct 26 ms 3960 KB Correct.
3 Correct 24 ms 3876 KB Correct.
4 Correct 22 ms 5152 KB Correct.
5 Correct 20 ms 3512 KB Correct.

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3924 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 2800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 2772 KB Time limit exceeded
2 Halted 0 ms 0 KB -