oj.uz

Submission #881650

# Submission time Handle Problem Language Result Execution time Memory
881650 2023-12-01T16:44:45 Z tsumondai Cyberland (APIO23_cyberland) C++17
100 / 100
 839 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 = 1e105;
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 23 ms 2908 KB Correct.
2 Correct 17 ms 2908 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2904 KB Correct.
2 Correct 25 ms 2904 KB Correct.
3 Correct 27 ms 2908 KB Correct.
4 Correct 24 ms 2908 KB Correct.
5 Correct 28 ms 3160 KB Correct.
6 Correct 24 ms 3532 KB Correct.
7 Correct 29 ms 3676 KB Correct.
8 Correct 13 ms 4416 KB Correct.
9 Correct 22 ms 2868 KB Correct.
10 Correct 21 ms 2652 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2932 KB Correct.
2 Correct 26 ms 2904 KB Correct.
3 Correct 24 ms 2908 KB Correct.
4 Correct 26 ms 2896 KB Correct.
5 Correct 26 ms 2652 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 8052 KB Correct.
2 Correct 141 ms 3924 KB Correct.
3 Correct 124 ms 3840 KB Correct.
4 Correct 128 ms 3768 KB Correct.
5 Correct 73 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Correct.
2 Correct 21 ms 3160 KB Correct.
3 Correct 25 ms 2980 KB Correct.
4 Correct 21 ms 3680 KB Correct.
5 Correct 17 ms 2652 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2920 KB Correct.
2 Correct 19 ms 3888 KB Correct.
3 Correct 32 ms 10352 KB Correct.
4 Correct 18 ms 4184 KB Correct.
5 Correct 21 ms 3672 KB Correct.
6 Correct 20 ms 4008 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2988 KB Correct.
2 Correct 17 ms 3064 KB Correct.
3 Correct 307 ms 13448 KB Correct.
4 Correct 213 ms 7004 KB Correct.
5 Correct 310 ms 10344 KB Correct.
6 Correct 116 ms 8788 KB Correct.
7 Correct 214 ms 6976 KB Correct.
8 Correct 165 ms 5200 KB Correct.
9 Correct 71 ms 3776 KB Correct.
10 Correct 64 ms 3928 KB Correct.
11 Correct 152 ms 4948 KB Correct.
12 Correct 82 ms 3868 KB Correct.
13 Correct 76 ms 3920 KB Correct.
14 Correct 209 ms 8424 KB Correct.
15 Correct 192 ms 5980 KB Correct.
16 Correct 70 ms 3920 KB Correct.
17 Correct 94 ms 4016 KB Correct.
18 Correct 80 ms 3928 KB Correct.
19 Correct 244 ms 4828 KB Correct.
20 Correct 5 ms 2908 KB Correct.
21 Correct 7 ms 2908 KB Correct.
22 Correct 11 ms 3420 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2932 KB Correct.
2 Correct 27 ms 3160 KB Correct.
3 Correct 167 ms 13144 KB Correct.
4 Correct 245 ms 5456 KB Correct.
5 Correct 653 ms 10484 KB Correct.
6 Correct 220 ms 8696 KB Correct.
7 Correct 378 ms 8712 KB Correct.
8 Correct 183 ms 5076 KB Correct.
9 Correct 128 ms 3716 KB Correct.
10 Correct 108 ms 3708 KB Correct.
11 Correct 111 ms 3980 KB Correct.
12 Correct 153 ms 3868 KB Correct.
13 Correct 135 ms 3924 KB Correct.
14 Correct 839 ms 9156 KB Correct.
15 Correct 637 ms 8964 KB Correct.
16 Correct 345 ms 6460 KB Correct.
17 Correct 215 ms 5140 KB Correct.
18 Correct 120 ms 3920 KB Correct.
19 Correct 163 ms 3924 KB Correct.
20 Correct 134 ms 3920 KB Correct.
21 Correct 482 ms 4812 KB Correct.
22 Correct 7 ms 2904 KB Correct.
23 Correct 11 ms 2904 KB Correct.
24 Correct 16 ms 3420 KB Correct.