oj.uz

Submission #749650

# Submission time Handle Problem Language Result Execution time Memory
749650 2023-05-28T10:46:32 Z happypotato Cyberland (APIO23_cyberland) C++17
44 / 100
 3000 ms 39296 KB 
#include "cyberland.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double
#pragma GCC optimize("Ofast")
 
const int mxN = 1e5 + 1;
vector<pii> adj[mxN];
short special[mxN];
int n, k, h;
 
bool cango[mxN];
 
void FindConnected() {
	queue<int> q;
	q.push(0); cango[0] = true;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		if (cur == h) continue;
		for (pii &v : adj[cur]) {
			if (!cango[v.ff]) {
				q.push(v.ff);
				cango[v.ff] = true;
			}
		}
	}
}
 
const int mxK = 70;
double dist[mxN][mxK];
priority_queue<pair<double, pii>, vector<pair<double, pii>>, greater<pair<double, pii>>> pq;
const double INF = 1e18, EPS = 1e-8;
void FindAnswer() {
	while (!pq.empty()) pq.pop();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= min(k, mxK - 1); j++) {
			dist[i][j] = INF;
		}
	}
	dist[h][0] = 0;
	pq.push({0, {h, 0}});
	bool start = true;
	while (!pq.empty()) {
		pair<double, pii> cur = pq.top();
		pq.pop();
		// if (cur.ss.ss <= 3) {
		// 	cerr << "DIJK " << cur.ff << ' ' << cur.ss.ff << ' ' << cur.ss.ss << endl;
		// }
		if (cur.ff > dist[cur.ss.ff][cur.ss.ss]) continue;
      	if (!start && cur.ss.ff == h) continue;
      	start = false;
		double ncur;
		for (pii &v : adj[cur.ss.ff]) {
			ncur = cur.ff + v.ss;
			if (ncur < dist[v.ff][cur.ss.ss]) {
				dist[v.ff][cur.ss.ss] = ncur;
				pq.push({ncur, {v.ff, cur.ss.ss}});
			}
			if (special[v.ff] == 2 && cur.ss.ss + 1 < mxK) {
				ncur /= 2;
				if (ncur < dist[v.ff][cur.ss.ss + 1]) {
					dist[v.ff][cur.ss.ss + 1] = ncur;
					pq.push({ncur, {v.ff, cur.ss.ss + 1}});
				}
			}
		}
	}
}
 
double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr) {
	n = N; k = K; h = H;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		cango[i] = false;
	}
	for (int i = 0; i < M; i++) {
		adj[X[i]].pb({Y[i], C[i]});
		adj[Y[i]].pb({X[i], C[i]});
	}
	for (int i = 0; i < n; i++) {
		special[i] = arr[i];
	}
	// assert(special[0] == 1 && special[h] == 1);
 
	FindConnected();
	if (!cango[h]) return -1;
 
	// cerr << setprecision(1) << fixed;
	FindAnswer();
	// cerr << "DEBUG:\n";
	// for (int i = 0; i < n; i++) {
	// 	cerr << "NODE " << i << ": ";
	// 	for (int j = 0; j < 3; j++) cerr << dist[i][j] << ' ';
	// 	cerr << endl;
	// }
	double res = 1e18;
	for (int i = 0; i <= min(k, mxK - 1); i++) {
    	for (int j = 0; j < n; j++) {
        	if (cango[j] && (j == 0 || special[j] == 0)) {
            	res = min(res, dist[j][i]);
            }
        }
	}
	return res;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 2772 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3380 KB Correct.
2 Correct 28 ms 3412 KB Correct.
3 Correct 27 ms 3360 KB Correct.
4 Correct 27 ms 3284 KB Correct.
5 Correct 26 ms 3412 KB Correct.
6 Correct 27 ms 8908 KB Correct.
7 Correct 37 ms 8876 KB Correct.
8 Correct 20 ms 15124 KB Correct.
9 Correct 24 ms 2796 KB Correct.
10 Correct 24 ms 2788 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3364 KB Correct.
2 Correct 31 ms 3284 KB Correct.
3 Correct 27 ms 3412 KB Correct.
4 Correct 29 ms 2768 KB Correct.
5 Correct 29 ms 2784 KB Correct.
6 Correct 9 ms 7780 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 39296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3520 KB Correct.
2 Correct 31 ms 3448 KB Correct.
3 Correct 25 ms 3392 KB Correct.
4 Correct 31 ms 9292 KB Correct.
5 Correct 20 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3440 KB Correct.
2 Correct 21 ms 3456 KB Correct.
3 Correct 42 ms 9376 KB Correct.
4 Correct 19 ms 6868 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 23 ms 3412 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 9472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 27900 KB Time limit exceeded
2 Halted 0 ms 0 KB -