oj.uz

Submission #1067485

# Submission time Handle Problem Language Result Execution time Memory
1067485 2024-08-20T17:53:20 Z lovrot Cyberland (APIO23_cyberland) C++17
8 / 100
 351 ms 44884 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, P - 1) : p;
			if(!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);
	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 20 ms 6748 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9560 KB Correct.
2 Correct 27 ms 9652 KB Correct.
3 Correct 21 ms 9560 KB Correct.
4 Correct 22 ms 9564 KB Correct.
5 Correct 21 ms 9604 KB Correct.
6 Correct 20 ms 16212 KB Correct.
7 Correct 25 ms 16476 KB Correct.
8 Correct 13 ms 20788 KB Correct.
9 Correct 20 ms 7260 KB Correct.
10 Correct 19 ms 7256 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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