Submission #1200263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200263		crispxx	사이버랜드 (APIO23_cyberland)	C++20	97 / 100	3097 ms	158244 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

// #include "stub.cpp"

struct DSU {
	int n; vector<int> p, sz;
	DSU(int n) : p(n), sz(n, 1) {
		iota(all(p), 0);
	}
	int find(int v) {
		return v == p[v] ? v : p[v] = find(p[v]);
	}
	bool unite(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return false;
		if(sz[u] < sz[v]) swap(u, v);
		p[v] = u;
		sz[u] += sz[v];
		return true;
	}
};

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<vector<ar<int, 2>>> adj(n);
	DSU dsu(n);
	for(int i = 0; i < m; i++) {
		adj[x[i]].pb({y[i], c[i]});
		adj[y[i]].pb({x[i], c[i]});
		if(x[i] != h && y[i] != h) {
			dsu.unite(x[i], y[i]);
		}
	}
	
	k = min(k, 70);
	
	vector<vector<double>> d(n, vector<double>(k + 1, 1e18));
	
	priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> pq;
	d[0][0] = 0;
	pq.push({0, 0, 0});
	for(int i = 0; i < n; i++) {
		if(a[i] == 0 && dsu.find(0) == dsu.find(i)) {
			d[i][0] = 0;
			pq.push({0, 0, i});
		} 
	}
	
	while(!pq.empty()) {
		auto [d_v_k, k, v] = pq.top();
		pq.pop();
		if(d_v_k != d[v][k] || v == h) continue;
		for(auto [to, c] : adj[v]) {
			if(d[to][k] > d[v][k] + c) {
				d[to][k] = d[v][k] + c;
				pq.push({d[to][k], k, to});
			}
			if(a[to] == 2 && d[to][k + 1] > (d[v][k] + c) / 2) {
				d[to][k + 1] = (d[v][k] + c) / 2;
				pq.push({d[to][k + 1], k + 1, to});
			}
		}
	}
	
	double ans = 1e18;
	for(int i = 0; i <= k; i++) {
		ans = min(ans, d[h][i]);
	}
	
	if(ans == 1e18) ans = -1;
	
	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: 0 / 3