Submission #1195464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195464		Shadow1	Cyberland (APIO23_cyberland)	C++20	100 / 100	1422 ms	136644 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define pb push_back
#define eb emplace_back
#define pii pair<ll, ll>
#define pdd pair<ld, ld>
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());

const ll maxn = 1e5 + 5;
const ll INF = 1e15;
vector<bool> vis(maxn);
vector<pii> adj[maxn];

ll n, m, h, k;
void dfs(int u) {
	vis[u] = true;
	if(u == h) return;
	for(auto &v : adj[u]) {
		if(!vis[v.fir]) dfs(v.fir);
	}
}

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> arr) {
    n = N, m = M, h = H, k = K;
    k = min(k, 70ll);
    for(int i=0; i<m; ++i) {
		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}
	dfs(0);
	
	vector<int> s = {0};  // source nodes
	for(int i=1; i<n; ++i) {
		if(arr[i] == 0 && vis[i])
			s.push_back(i);
	}
	// output_vector(s);
	vector<vector<ld>> dist(n, vector<ld>(k+5, INF));
	priority_queue<pair<ld, int>, vector<pair<ld, int>>, greater<pair<ld, int>>> pq;
	for(auto &S : s){
		for(int i=0; i<=k; ++i)
			dist[S][i] = 0;
	}
	for(int t=0; t<=k; ++t) {
		for(int i=0; i<n; ++i) {
			if(dist[i][t] < INF) 
				pq.push({dist[i][t], i});
		}
		while(!pq.empty()) {
			ld w = pq.top().fir;
			ll u = pq.top().sec;
			pq.pop();
			// show(u);
			if(w > dist[u][t] || u == h) continue;
			for(auto &v : adj[u]) {
				if(arr[v.fir] == 0 && dist[v.fir][t] > 0) {
					dist[v.fir][t] = 0;
					pq.push({0, v.fir});
					continue;
				}
				if(arr[v.fir] == 2 && (dist[u][t] + v.sec) / 2.0 < dist[v.fir][t+1]) {
					dist[v.fir][t+1] = (dist[u][t] + v.sec) / 2.0;
					// pq.push({dist[v.fir][t+1], v.fir});
				}
				if(dist[u][t] + v.sec < dist[v.fir][t]) {
					dist[v.fir][t] = dist[u][t] + v.sec;
					pq.push({dist[v.fir][t], v.fir});
				}
			}
		}
	}
	ld ans = INF;
	for(int i=0; i<=k; ++i)
		ans = min(ans, dist[h][i]);
	if(!vis[h]) ans = -1;
	for(int i=0; i<n; ++i) {
		vis[i] = false;
		adj[i].clear();
	}
	return ans;
}

• 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