Submission #1211439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211439		k1r1t0	Cyberland (APIO23_cyberland)	C++20	8 / 100	627 ms	13400 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];
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]});
	}
	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++)
				if (dist[i] < INF && arr[i - 1] == 2)
					dist[i] /= 2;
		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});
			}
		}
	}
	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: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3