oj.uz

Submission #983260

# Submission time Handle Problem Language Result Execution time Memory
983260 2024-05-15T09:48:48 Z c2zi6 Cyberland (APIO23_cyberland) C++17
97 / 100
 1902 ms 2097152 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 50 ms 740 KB Correct.
2 Correct 64 ms 744 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Runtime error 1137 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -