Submission #1211442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211442		k1r1t0	Cyberland (APIO23_cyberland)	C++20	100 / 100	2140 ms	22432 KiB

cyberland

#include <bits/stdc++.h>

using namespace std;
#define ld long double

const int N = 110000;
const int MK = 70;
const ld INF = 1e18;

ld dist[N], old[N];
vector<array<int, 2>> g[N];

void dfs(int v) {
	if (dist[v] == 0)
		return;
	dist[v] = 0;
	for (auto [u, w] : g[v])
		dfs(u);
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	K = min(K, MK);
	H++;
	for (int i = 1; i <= N; i++)
		g[i].clear();
	for (int i = 0; i < M; i++) {
		g[x[i] + 1].push_back({y[i] + 1, c[i]});
		g[y[i] + 1].push_back({x[i] + 1, c[i]});
	}
	g[H].clear();
	for (int i = 1; i <= N; i++)
		dist[i] = INF;
	dfs(1);
	for (int i = 1; i <= N; i++)
		if (dist[i] == 0 && arr[i - 1] != 0 && i != 1)
			dist[i] = INF;
	for (int t = 0; t <= K; t++) {
		if (t > 0) {
			for (int i = 1; i <= N; i++) {
				old[i] = dist[i];
				if (old[i] < INF && arr[i - 1] == 2)
					old[i] /= 2;
				dist[i] = INF;
			}
			for (int i = 1; i <= N; i++)
				if (old[i] < INF) {
					if (arr[i - 1] == 2)
						for (auto [u, w] : g[i])
							dist[u] = min(dist[u], old[i] + w);
					else
						dist[i] = min(dist[i], old[i]);
				}
		}
		set<pair<ld, int>> st;
		for (int i = 1; i <= N; i++)
			if (dist[i] < INF)
				st.insert({dist[i], i});	
		while (!st.empty()) {
			auto [d, v] = *st.begin(); st.erase(st.begin());
			for (auto [u, w] : g[v]) if (d + w < dist[u]) {
				st.erase({dist[u], u});
				dist[u] = d + w;
				st.insert({dist[u], u});
			}
		}
	}
	if (dist[H] == INF) return -1;
	return dist[H];
}

/*
#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}
//*/

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3