oj.uz

Submission #1067491

# Submission time Handle Problem Language Result Execution time Memory
1067491 2024-08-20T18:04:20 Z lovrot Cyberland (APIO23_cyberland) C++17
21 / 100
 356 ms 39112 KB 
#include "cyberland.h"
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int P = 60;
const int N = 1e5 + 10;
const double OO = 1e18;
const double TSH = 1e-9;

int k, n, h;
vector<pii> g[N];

char con[N], bio[N][P], type[N];
double dp[N][P], ans;
set<pair<double, pii>> s;

void check(int u) { 
	if(con[u]) { 
		return;
	}
	con[u] = 1;
	if(u == h) {
		return; 
	}
	for(pii e : g[u]) { 
		check(e.X);
	}
}

void dijkstra() {
	for(int i = 0; i < n; ++i) { 
		for(int j = 0; j < P; ++j) { 
			dp[i][j] = OO;
			bio[i][j] = 0;
		}
	}

	dp[h][0] = 0;
	s.insert({dp[h][0], {h, 0}});

	for(; !s.empty(); ) { 
		int u = s.begin()->Y.X;
		int p = s.begin()->Y.Y;
		s.erase(s.begin());
		if(bio[u][p] || type[u] == 0) { 
			ans = min(ans, dp[u][p]);
		}
		bio[u][p] = 1;
		for(pii e : g[u]) { 
			int v = e.X, w = e.Y, pp = type[v] == 2 ? min(p + 1, k) : p;
			if(con[v] && !bio[v][pp] && abs(dp[v][pp] - dp[u][p] - (double) w / (1LL << p)) > TSH) { 
				dp[v][pp] = dp[u][p] + (double) w / (1LL << p);
				s.insert({dp[v][pp], {v, pp}});
			}
		}
	}
}

double solve(int nn, int m, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	n = nn;
	k = min(kk, P - 1);
	h = hh;

	for(int i = 0; i < n; ++i) { 
		con[i] = 0;
		g[i].clear();
	}

	for(int i = 0; i < m; ++i) {
		g[x[i]].PB({y[i], c[i]});
		g[y[i]].PB({x[i], c[i]});
	}
	for(int i = 0; i < n; ++i) { 
		type[i] = arr[i];
	}
	type[0] = 0;

	check(0);
	
	if(!con[h]) { 
		return -1;
	}
	
	ans = OO;
	dijkstra();
    return ans;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3416 KB Correct.
2 Correct 20 ms 4988 KB Correct.
3 Correct 20 ms 4956 KB Correct.
4 Correct 20 ms 3416 KB Correct.
5 Correct 27 ms 3420 KB Correct.
6 Correct 20 ms 8740 KB Correct.
7 Correct 25 ms 10164 KB Correct.
8 Correct 15 ms 16220 KB Correct.
9 Correct 18 ms 4492 KB Correct.
10 Correct 17 ms 4440 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3420 KB Correct.
2 Correct 20 ms 5784 KB Correct.
3 Correct 19 ms 4224 KB Correct.
4 Correct 19 ms 3684 KB Correct.
5 Correct 19 ms 3672 KB Correct.
6 Correct 7 ms 7772 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39112 KB Correct.
2 Incorrect 23 ms 5972 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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