Submission #1050889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050889		vjudge1	Cyberland (APIO23_cyberland)	C++17	100 / 100	262 ms	169668 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
const int N = 2e5 + 20;

namespace DSU{
	int p[N];
	void init(int n){
		iota(p, p + n + 1, 0);
	}
	int find(int x){
		if(p[x] == x)return x;
		return p[x] = find(p[x]);
	}
	bool join(int u,int v){
		u = find(u), v = find(v);
		if(u == v)return 0;
		p[u] = v;
		return 1;
	}
};
ld dist[N][100];
priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>> pq;

void push(int k,int x, ld d){
	if(dist[x][k] > d){
		dist[x][k] = d;
		pq.push({d, {x, k}});
	}
}

double solve(int n, int m, int K, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> A) {
	vector<ar<int, 2>> g[n];;
	K = min(K, 69);
	DSU::init(n);
	for(int i = 0;i < m;i++){
		if(x[i] != h && y[i] != h)DSU::join(x[i], y[i]);
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	ld pow[K + 1];
	pow[0] = 1;
	for(int i = 1;i <= K;i++)pow[i] = pow[i - 1] / 2;
	A[0] = 0;
	pq = priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>>();
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= K;j++){
			dist[i][j] = 1e18;
		}
	}
	push(K, h, 0);
	while(pq.size()){
		ld d = pq.top().first;
		auto [x, k] = pq.top().second;
		pq.pop();
		if(dist[x][k] < d)continue;
		if(A[x] == 0)return d;
		for(auto [u, c]: g[x]){
			if(DSU::find(u) != DSU::find(0))continue;
			push(k, u, d + c * pow[K - k]);
			if(A[x] == 2 && k > 0)push(k - 1, u, d + c * pow[K - k + 1]);
		}
	}
    return -1;
}

• 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