답안 #983260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983260	2024-05-15T09:48:48 Z	c2zi6	사이버랜드 (APIO23_cyberland)	C++17	97 / 100	1902 ms	2097152 KB

cyberland

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "cyberland.h"

namespace DANDAX {
	typedef vector<vector<pair<int, ld>>> GRAPH;
	int n, m, k, h;
	GRAPH gp;
	VI col;
	typedef vector<ld> VD;
	typedef vector<VD> VVD;
	double sol(int N, int M, int K, int H, VI X, VI Y, VI C, VI ARR) {
		n = N, m = M, k = K, h = H;
		col = ARR;
		gp = GRAPH(n * (k+1));
		rep(i, m) {
			int u = X[i];
			int v = Y[i];
			ld w = C[i];
			gp[u].pb({v, w});
			gp[v].pb({u, w});
			replr(l, 0, k) {
				gp[u + n*l].pb({v + n*l, w});
				gp[v + n*l].pb({u + n*l, w});
				w /= 2;
			}
		}
		
		ld ans = 1e18;
		VD cur(n, 1e18);
		cur[0] = 0;
		for (int i = 0; i < 10; i++) {
			VD nxt(n, 1e18);
			rep(u, n) if (u != h) {
				for (auto[v, w] : gp[u]) {
					setmin(nxt[v], cur[u] + w);
				}
			}
			rep(u, n) if (col[u] == 2) if (nxt[u] != 1e18) nxt[u] /= 2;
			rep(u, n) if (col[u] == 0) if (nxt[u] != 1e18) nxt[u] = 0;
			cur = nxt;
			setmin(ans, cur[h]);
		}
		if (ans == 1e18) return -1;
		return ans;
	}
}

typedef vector<vector<pair<int, ld>>> GRAPH;

int n, h;
void dijkstra(GRAPH& gp, vector<ld>& dist, int s) {
	int n = gp.size();
	priority_queue<pair<ld, int>> pq;
	dist = vector<ld>(n, 1e18);
	dist[s] = 0;
	pq.push({0, s});
	VI vis(n);
	while (pq.size()) {
		int u = pq.top().ss;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto[v, w] : gp[u]) {
			if (v%(::n) == h) continue;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				pq.push({-dist[v], v});
			}
		}
	}
}

int m, k;
GRAPH gp;
VI col;

ld ans;

VI vis;
void dfs(int u, vector<ld>& dist) {
	if (u%n == h) return;
	if (col[u%n] == 0) setmin(ans, dist[u]);
	vis[u] = true;
	for (auto[v, w] : gp[u]) if (!vis[v]) dfs(v, dist);
}

double solve(int N, int M, int K, int H, VI X, VI Y, VI C, VI ARR) {
	n = N, m = M, k = K, h = H;
	setmin(K, 31);
	col = ARR;
	gp = GRAPH(n * (k+1));
	rep(i, m) {
		int u = X[i];
		int v = Y[i];
		ld w = C[i];
		replr(l, 0, k) {
			gp[u + n*l].pb({v + n*l, w});
			gp[v + n*l].pb({u + n*l, w});
			w /= 2;
		}
	}

	rep(u, n) if (col[u] == 2) {
		ld dv = 2;
		replr(l, 0, k-1) {
			for (auto[v, w] : gp[u]) if (v < n) {
				gp[u + l*n].pb({v + n*(l+1), w/dv});
				/* cout << "KOX: " << u + l*n << " " << v + n*(l+1) << " " << w/dv << endl; */
			}
			dv *= 2;
		}
	}

	vector<ld> dist;
	dijkstra(gp, dist, h);
	/* for (ld x : dist) cout << x << " "; */
	/* cout << endl; */
	if (dist[0] == 1e18) return -1;
	col[0] = 0;
	vis = VI(gp.size());
	ans = 1e18;
	dfs(0, dist);

    return ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	740 KB	Correct.
2	Correct	64 ms	744 KB	Correct.

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	139 ms	5788 KB	Correct.
2	Correct	230 ms	5968 KB	Correct.
3	Correct	163 ms	5868 KB	Correct.
4	Correct	183 ms	6368 KB	Correct.
5	Correct	178 ms	6336 KB	Correct.
6	Correct	308 ms	41488 KB	Correct.
7	Correct	371 ms	41540 KB	Correct.
8	Correct	176 ms	80720 KB	Correct.
9	Correct	148 ms	1820 KB	Correct.
10	Correct	155 ms	1936 KB	Correct.

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	169 ms	5884 KB	Correct.
2	Correct	166 ms	5992 KB	Correct.
3	Correct	151 ms	6028 KB	Correct.
4	Correct	153 ms	2012 KB	Correct.
5	Correct	153 ms	1888 KB	Correct.
6	Correct	48 ms	33360 KB	Correct.

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1138 ms	274800 KB	Correct.
2	Correct	341 ms	8344 KB	Correct.
3	Correct	356 ms	7760 KB	Correct.
4	Correct	329 ms	7436 KB	Correct.
5	Correct	324 ms	2012 KB	Correct.

Subtask #5
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	139 ms	4792 KB	Correct.
2	Correct	204 ms	5252 KB	Correct.
3	Correct	156 ms	5548 KB	Correct.
4	Correct	229 ms	40532 KB	Correct.
5	Correct	129 ms	976 KB	Correct.

Subtask #6
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	154 ms	5360 KB	Correct.
2	Correct	142 ms	5516 KB	Correct.
3	Correct	1124 ms	322612 KB	Correct.
4	Correct	140 ms	36720 KB	Correct.
5	Correct	145 ms	1944 KB	Correct.
6	Correct	147 ms	6176 KB	Correct.

Subtask #7
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	335 ms	5776 KB	Correct.
2	Correct	60 ms	9236 KB	Correct.
3	Correct	1462 ms	229420 KB	Correct.
4	Correct	865 ms	65216 KB	Correct.
5	Correct	1902 ms	341736 KB	Correct.
6	Correct	1037 ms	304776 KB	Correct.
7	Correct	820 ms	61716 KB	Correct.
8	Correct	485 ms	12812 KB	Correct.
9	Correct	313 ms	6792 KB	Correct.
10	Correct	291 ms	6500 KB	Correct.
11	Correct	452 ms	5876 KB	Correct.
12	Correct	346 ms	7200 KB	Correct.
13	Correct	338 ms	6968 KB	Correct.
14	Correct	812 ms	55116 KB	Correct.
15	Correct	606 ms	25132 KB	Correct.
16	Correct	337 ms	6848 KB	Correct.
17	Correct	372 ms	7236 KB	Correct.
18	Correct	328 ms	6556 KB	Correct.
19	Correct	882 ms	8832 KB	Correct.
20	Correct	26 ms	1320 KB	Correct.
21	Correct	26 ms	4480 KB	Correct.
22	Correct	72 ms	35000 KB	Correct.

Subtask #8
0.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1137 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

답안 #983260

Compilation message