Submission #760040

#	Time	Username	Problem	Language	Result	Execution time	Memory
760040		8e7	Cyberland (APIO23_cyberland)	C++17	100 / 100	1636 ms	16084 KiB

cyberland

#include "cyberland.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define ld double
#define maxn 100005
#define ff first
#define ss second
#define pii pair<ll, ll>
const ld inf = 1e15;
const ld eps = 1e-10;
vector<pii> adj[maxn];
int type[maxn];
ld d[maxn], d2[maxn];
void dijkstra(int n) {
	priority_queue<pair<ld, int> , vector<pair<ld, int> >, greater<pair<ld, int> > > pq;
	for (int i = 0;i < n;i++) {
		d2[i] = d[i];
		if (d[i] != inf) {
			pq.push(make_pair(d[i], i));
		}
	}
	while (pq.size()) {
		auto [dis, cur] = pq.top();pq.pop();
		if (abs(dis - d[cur]) > eps) continue;
		for (auto [v, w]:adj[cur]) {
			if (type[v] == 0 && d[v] > 0) {
				d[v] = 0;
				pq.push(make_pair(0, v));
			}
			if (d[cur] + w < d[v]) {
				d[v] = d[cur]+w;
				pq.push(make_pair(d[v], v));
			}
			if (type[v] == 2 && (d[cur] + w) / 2 < d2[v]) {
				d2[v] = (d[cur] + w) / 2;
			}
		}
	}
	pary(d, d + n);
	pary(d2, d2+n);
}
double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr) {
	for (int i = 0;i < N;i++) {
		adj[i].clear();
		d[i] = d2[i] = inf;
		type[i] = arr[i];
	}
	for (int i = 0;i < M;i++) {
		if (U[i] == H) swap(U[i], V[i]);	
		adj[U[i]].push_back({V[i], W[i]});
		if (V[i] != H) adj[V[i]].push_back({U[i], W[i]});
	}
	d[0] = d2[0] = 0;
	for (int i = 0;i <= min(K, 100);i++) {
		dijkstra(N);
		if (i < K) {
			for (int j = 0;j < N;j++) {
				d[j] = min(d[j], d2[j]);
			}
		}
	}	
	if (d[H] == inf) {
		return -1;
	}
	return d[H];
}

Compilation message (stderr)

cyberland.cpp: In function 'void dijkstra(int)':
cyberland.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
cyberland.cpp:52:2: note: in expansion of macro 'pary'
   52 |  pary(d, d + n);
      |  ^~~~
cyberland.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
cyberland.cpp:53:2: note: in expansion of macro 'pary'
   53 |  pary(d2, d2+n);
      |  ^~~~

• 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