oj.uz

Submission #881652

# Submission time Handle Problem Language Result Execution time Memory
881652 2023-12-01T16:45:46 Z tsumondai Cyberland (APIO23_cyberland) C++17
100 / 100
 807 ms 13448 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

using vi = vector<int>;
using ar = pair<double,int>;

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
typedef pair<double, int> ar;

const int N = 1e5 + 10;

const double oo = DBL_MAX;
int n, m, h;
double ans = 0;
bool vis[N];
double dis[N], dis2[N];
vector<ii> adj[N];
priority_queue<ar, vector<ar>, greater<ar>> pq;

void dijkstra(){
	fill(vis,vis+n+1,0);
	for(int i = 0; i < n; i++) 
		if(dis[i]<oo) pq.push({dis[i],i});
	while(!pq.empty()){
		auto tmp = pq.top(); pq.pop(); 
		double D=tmp.fi; int a=tmp.se;
		if(vis[a] || a==h) continue; vis[a]=1;
		for(auto tmp : adj[a]) {
			int b=tmp.fi, w=tmp.se;
			if(dis[b]>dis[a]+w) 
			dis[b]=dis[a]+w, pq.push({dis[b],b});
		}
	}
	ans = min(ans, dis[h]);
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi A) {
	n = N, m = M, h = H, K = min(K, 67);
	fill(dis, dis + n, oo); ans = oo;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < m; i++)
		adj[x[i]].push_back({y[i], c[i]}),
		    adj[y[i]].push_back({x[i], c[i]});
	dis[0] = 0; dijkstra(); if (dis[h] >= oo) return -1;
	for (int i = 0; i < n; i++)
		if (dis[i] != oo) dis[i] = A[i] && i ? oo : 0;
	for (int i = 0; i <= K; i++) {
		dijkstra(); fill(dis2, dis2 + n, oo);
		for (int j = 0; j < n; j++)
			if (A[j] > 1) for (auto tmp : adj[j]) {
				int u=tmp.fi, w=tmp.se;
				dis2[u] = min(dis2[u], dis[j] / 2 + w);
			}		
		for (int j = 0; j < n; j++) dis[j] = dis2[j];
	}
	return ans;
}

Compilation message

cyberland.cpp: In function 'void dijkstra()':
cyberland.cpp:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |   if(vis[a] || a==h) continue; vis[a]=1;
      |   ^~
cyberland.cpp:39:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |   if(vis[a] || a==h) continue; vis[a]=1;
      |                                ^~~
cyberland.cpp:38:10: warning: unused variable 'D' [-Wunused-variable]
   38 |   double D=tmp.fi; int a=tmp.se;
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3168 KB Correct.
2 Correct 18 ms 3160 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3824 KB Correct.
2 Correct 26 ms 3932 KB Correct.
3 Correct 24 ms 3932 KB Correct.
4 Correct 25 ms 3972 KB Correct.
5 Correct 35 ms 3920 KB Correct.
6 Correct 23 ms 4428 KB Correct.
7 Correct 40 ms 4852 KB Correct.
8 Correct 13 ms 4952 KB Correct.
9 Correct 22 ms 3676 KB Correct.
10 Correct 22 ms 3748 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3936 KB Correct.
2 Correct 37 ms 3920 KB Correct.
3 Correct 25 ms 3732 KB Correct.
4 Correct 25 ms 3684 KB Correct.
5 Correct 30 ms 3736 KB Correct.
6 Correct 6 ms 3756 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 9448 KB Correct.
2 Correct 146 ms 3932 KB Correct.
3 Correct 125 ms 3924 KB Correct.
4 Correct 128 ms 3924 KB Correct.
5 Correct 73 ms 3716 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3676 KB Correct.
2 Correct 21 ms 3928 KB Correct.
3 Correct 21 ms 3856 KB Correct.
4 Correct 25 ms 4740 KB Correct.
5 Correct 22 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3932 KB Correct.
2 Correct 19 ms 3836 KB Correct.
3 Correct 33 ms 10332 KB Correct.
4 Correct 14 ms 4188 KB Correct.
5 Correct 21 ms 3672 KB Correct.
6 Correct 21 ms 3932 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3776 KB Correct.
2 Correct 15 ms 3140 KB Correct.
3 Correct 316 ms 13448 KB Correct.
4 Correct 214 ms 6972 KB Correct.
5 Correct 320 ms 10188 KB Correct.
6 Correct 115 ms 8652 KB Correct.
7 Correct 216 ms 6852 KB Correct.
8 Correct 168 ms 5252 KB Correct.
9 Correct 69 ms 4088 KB Correct.
10 Correct 64 ms 3924 KB Correct.
11 Correct 147 ms 5044 KB Correct.
12 Correct 83 ms 3928 KB Correct.
13 Correct 77 ms 4000 KB Correct.
14 Correct 211 ms 8424 KB Correct.
15 Correct 190 ms 5972 KB Correct.
16 Correct 71 ms 4004 KB Correct.
17 Correct 92 ms 3872 KB Correct.
18 Correct 81 ms 3812 KB Correct.
19 Correct 245 ms 4948 KB Correct.
20 Correct 5 ms 2908 KB Correct.
21 Correct 7 ms 2908 KB Correct.
22 Correct 9 ms 3420 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4240 KB Correct.
2 Correct 26 ms 3144 KB Correct.
3 Correct 168 ms 13232 KB Correct.
4 Correct 229 ms 5492 KB Correct.
5 Correct 641 ms 10492 KB Correct.
6 Correct 226 ms 8708 KB Correct.
7 Correct 376 ms 8352 KB Correct.
8 Correct 195 ms 4864 KB Correct.
9 Correct 119 ms 3892 KB Correct.
10 Correct 106 ms 3908 KB Correct.
11 Correct 110 ms 3924 KB Correct.
12 Correct 143 ms 3796 KB Correct.
13 Correct 132 ms 3952 KB Correct.
14 Correct 807 ms 9240 KB Correct.
15 Correct 635 ms 9176 KB Correct.
16 Correct 342 ms 6588 KB Correct.
17 Correct 222 ms 5084 KB Correct.
18 Correct 117 ms 3924 KB Correct.
19 Correct 162 ms 3824 KB Correct.
20 Correct 135 ms 3920 KB Correct.
21 Correct 476 ms 5072 KB Correct.
22 Correct 7 ms 2908 KB Correct.
23 Correct 9 ms 2908 KB Correct.
24 Correct 16 ms 3496 KB Correct.