Submission #1067491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067491		lovrot	Cyberland (APIO23_cyberland)	C++17	21 / 100	356 ms	39112 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3