oj.uz

Submission #922454

# Submission time Handle Problem Language Result Execution time Memory
922454 2024-02-05T14:13:25 Z dozer Cyberland (APIO23_cyberland) C++17
100 / 100
 2272 ms 143324 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("curling.in", "r", stdin), freopen("curling.out", "w", stdout)
 
const long double INF = 2e18 + 7;

struct cmp{
    bool operator()(pair<long double, int> &a, pair<long double, int> &b){
        return a.st < b.st;
    }
};
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	int lim = min(K, 75);
	vector<vector<long double>> dist(lim + 5, vector<long double>(N, INF));
	vector<pii> adj[N + 5];
	for (int i = 0; i < M; i++){
		adj[x[i]].pb({y[i], c[i]});
		adj[y[i]].pb({x[i], c[i]});
	}
	vector<int> mark(N + 5, 0);
	queue<int> q;
	q.push(0);
	mark[0] = 1;
	while(!q.empty()){
		int top = q.front();
		q.pop();
		for (auto i : adj[top]){
			if (mark[i.st] == 0){
				mark[i.st] = 1;
				if (i.st != H) q.push(i.st);
			}
		}
	}
 
	dist[0][H] = 0;
	long double mini = INF;
	for (int i = 0; i <= lim; i++){
		priority_queue<pair<long double, int>, vector<pair<long double, int>>, cmp> q;
        vector<int> vis(N, 0);
		for (int j = 0; j < N; j++){
			if (i == 0 || j != H) q.push({-dist[i][j], j});
		}
		
		while(!q.empty()){
			int top = q.top().nd;
			q.pop();
            if (vis[top]) continue;
            vis[top] = 1;
			int curr = i;
			if (arr[top] != 2 || i == lim){
				for (auto j : adj[top]){
					int v = j.st, w = j.nd;
                    int div = min(60, i);
					long double upd = (long double)w / (1LL<<div);
                    if (div < i) upd /= (1LL<<(i -div));
                    upd += dist[i][top];
					if (dist[i][v] > upd){
						dist[i][v] = upd;
						if (v != H) q.push({-upd, v});
					}
				}
			}
				
			else if (arr[top] == 2) {
				for (auto j : adj[top]){
					int v = j.st, w = j.nd;
                    int div = min(60, i + 1);
                    long double upd = (long double)w / (1LL<<div);
                    if (div < i + 1) upd /= (1LL<<(i + 1 - div));
                    upd += dist[i][top];
					if (dist[i + 1][v] > upd){
						dist[i + 1][v] = upd;
					}
				}	
			}
		}
		for (int j = 0; j < N; j++){
			if (mark[j] && arr[j] == 0) mini = min(mini, dist[i][j]);		
		}
		mini = min(mini, dist[i][0]);
	}
		
	if (mini >= 2e18) return -1;
	return mini;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:56:8: warning: unused variable 'curr' [-Wunused-variable]
   56 |    int curr = i;
      |        ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 532 KB Correct.
2 Correct 47 ms 536 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 1244 KB Correct.
2 Correct 146 ms 1192 KB Correct.
3 Correct 152 ms 1308 KB Correct.
4 Correct 143 ms 1192 KB Correct.
5 Correct 170 ms 1228 KB Correct.
6 Correct 163 ms 7736 KB Correct.
7 Correct 184 ms 7428 KB Correct.
8 Correct 89 ms 14864 KB Correct.
9 Correct 111 ms 740 KB Correct.
10 Correct 109 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 1220 KB Correct.
2 Correct 167 ms 1184 KB Correct.
3 Correct 132 ms 1360 KB Correct.
4 Correct 114 ms 704 KB Correct.
5 Correct 118 ms 712 KB Correct.
6 Correct 31 ms 6100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 41984 KB Correct.
2 Correct 164 ms 1124 KB Correct.
3 Correct 150 ms 1188 KB Correct.
4 Correct 157 ms 1220 KB Correct.
5 Correct 174 ms 600 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 1180 KB Correct.
2 Correct 139 ms 1160 KB Correct.
3 Correct 140 ms 1156 KB Correct.
4 Correct 145 ms 7468 KB Correct.
5 Correct 104 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1168 KB Correct.
2 Correct 127 ms 1140 KB Correct.
3 Correct 414 ms 57012 KB Correct.
4 Correct 132 ms 5108 KB Correct.
5 Correct 110 ms 728 KB Correct.
6 Correct 129 ms 1116 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1116 KB Correct.
2 Correct 46 ms 1880 KB Correct.
3 Correct 703 ms 50324 KB Correct.
4 Correct 477 ms 13220 KB Correct.
5 Correct 676 ms 29788 KB Correct.
6 Correct 288 ms 12132 KB Correct.
7 Correct 488 ms 13336 KB Correct.
8 Correct 353 ms 2664 KB Correct.
9 Correct 225 ms 1248 KB Correct.
10 Correct 219 ms 1116 KB Correct.
11 Correct 300 ms 1340 KB Correct.
12 Correct 267 ms 1240 KB Correct.
13 Correct 235 ms 1120 KB Correct.
14 Correct 397 ms 16716 KB Correct.
15 Correct 410 ms 4588 KB Correct.
16 Correct 229 ms 1252 KB Correct.
17 Correct 273 ms 1212 KB Correct.
18 Correct 243 ms 1244 KB Correct.
19 Correct 661 ms 1184 KB Correct.
20 Correct 13 ms 604 KB Correct.
21 Correct 22 ms 1004 KB Correct.
22 Correct 18 ms 1564 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 1736 KB Correct.
2 Correct 84 ms 2652 KB Correct.
3 Correct 2272 ms 143324 KB Correct.
4 Correct 562 ms 7436 KB Correct.
5 Correct 1611 ms 56052 KB Correct.
6 Correct 573 ms 21072 KB Correct.
7 Correct 845 ms 27728 KB Correct.
8 Correct 511 ms 3876 KB Correct.
9 Correct 576 ms 2960 KB Correct.
10 Correct 501 ms 2696 KB Correct.
11 Correct 274 ms 1776 KB Correct.
12 Correct 614 ms 2888 KB Correct.
13 Correct 540 ms 2720 KB Correct.
14 Correct 1809 ms 58144 KB Correct.
15 Correct 1854 ms 72836 KB Correct.
16 Correct 817 ms 24724 KB Correct.
17 Correct 561 ms 7260 KB Correct.
18 Correct 802 ms 2868 KB Correct.
19 Correct 605 ms 2936 KB Correct.
20 Correct 558 ms 2992 KB Correct.
21 Correct 1505 ms 3924 KB Correct.
22 Correct 28 ms 788 KB Correct.
23 Correct 76 ms 1856 KB Correct.
24 Correct 36 ms 2140 KB Correct.