oj.uz

Submission #983250

# Submission time Handle Problem Language Result Execution time Memory
983250 2024-05-15T09:45:27 Z c2zi6 Cyberland (APIO23_cyberland) C++17
97 / 100
 1980 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;
	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 600 KB Correct.
2 Correct 50 ms 800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5020 KB Correct.
2 Correct 167 ms 6032 KB Correct.
3 Correct 158 ms 5624 KB Correct.
4 Correct 184 ms 6252 KB Correct.
5 Correct 174 ms 5952 KB Correct.
6 Correct 296 ms 41516 KB Correct.
7 Correct 345 ms 41592 KB Correct.
8 Correct 176 ms 80604 KB Correct.
9 Correct 142 ms 2100 KB Correct.
10 Correct 136 ms 1796 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5076 KB Correct.
2 Correct 162 ms 6160 KB Correct.
3 Correct 148 ms 5996 KB Correct.
4 Correct 141 ms 2020 KB Correct.
5 Correct 149 ms 1896 KB Correct.
6 Correct 50 ms 33408 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 273600 KB Correct.
2 Correct 377 ms 8336 KB Correct.
3 Correct 338 ms 7968 KB Correct.
4 Correct 326 ms 7464 KB Correct.
5 Correct 333 ms 2012 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4772 KB Correct.
2 Correct 174 ms 6004 KB Correct.
3 Correct 175 ms 6304 KB Correct.
4 Correct 298 ms 41148 KB Correct.
5 Correct 131 ms 1788 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5336 KB Correct.
2 Correct 140 ms 5436 KB Correct.
3 Correct 1245 ms 322596 KB Correct.
4 Correct 145 ms 38520 KB Correct.
5 Correct 146 ms 1844 KB Correct.
6 Correct 148 ms 6176 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 5816 KB Correct.
2 Correct 75 ms 9264 KB Correct.
3 Correct 1448 ms 229416 KB Correct.
4 Correct 894 ms 65084 KB Correct.
5 Correct 1980 ms 341820 KB Correct.
6 Correct 1010 ms 305072 KB Correct.
7 Correct 871 ms 61840 KB Correct.
8 Correct 479 ms 12816 KB Correct.
9 Correct 314 ms 6704 KB Correct.
10 Correct 326 ms 6496 KB Correct.
11 Correct 462 ms 5608 KB Correct.
12 Correct 345 ms 6860 KB Correct.
13 Correct 337 ms 6972 KB Correct.
14 Correct 803 ms 55296 KB Correct.
15 Correct 629 ms 25140 KB Correct.
16 Correct 324 ms 6664 KB Correct.
17 Correct 377 ms 7248 KB Correct.
18 Correct 329 ms 6564 KB Correct.
19 Correct 841 ms 8880 KB Correct.
20 Correct 26 ms 1068 KB Correct.
21 Correct 26 ms 4476 KB Correct.
22 Correct 81 ms 35352 KB Correct.

Subtask #8
0.0 / 3.0

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