oj.uz

Submission #749946

# Submission time Handle Problem Language Result Execution time Memory
749946 2023-05-29T02:03:41 Z jamezzz Cyberland (APIO23_cyberland) C++17
100 / 100
 1484 ms 67624 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define EPS 1e-9
#define INF 1023456789
#define LINF 1023456789123456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define disc(x) x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef vector<ii> vii;
typedef pair<double,int> di;
typedef tuple<double,int,int> dii;

#define maxn 100005
#define maxk 75

double dist[maxn][maxk];
vector<ii> AL[maxn];

double solve(int N,int M,int K,int H,vi x,vi y,vi c,vi arr){
	K=min(K,70);
    priority_queue<di,vector<di>,greater<di>> pq;
    for(int i=0;i<N;++i){
		for(int j=0;j<=K;++j)dist[i][j]=LINF;
		AL[i].clear();
	}
	dist[0][0]=0;
    for(int i=0;i<M;++i){
		AL[x[i]].pb({y[i],c[i]});
		AL[y[i]].pb({x[i],c[i]});
	}
	for(int k=0;k<=K;++k){
		for(int i=0;i<N;++i){
			if(dist[i][k]!=LINF)pq.push({dist[i][k],i});
		}		
		while(!pq.empty()){
			auto[d,u]=pq.top();pq.pop();
			if(abs(dist[u][k]-d)>EPS||u==H)continue;
			for(auto[v,w]:AL[u]){
				if(arr[v]==0&&dist[v][k]>0){
					dist[v][k]=0;
					pq.push({0,v});
					continue;
				}
				if(arr[u]==2&&k<K&&dist[v][k+1]>d/2+w){
					dist[v][k+1]=min(dist[v][k+1],d/2+w);
				}
				if(dist[v][k]>d+w){
					dist[v][k]=d+w;
					pq.push({dist[v][k],v});
				}
			}
		}
	}
	double ans=LINF;
	for(int i=0;i<=K;++i)ans=min(ans,dist[H][i]);
	return ans==LINF?-1:ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2772 KB Correct.
2 Correct 21 ms 2796 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3372 KB Correct.
2 Correct 27 ms 3372 KB Correct.
3 Correct 32 ms 3380 KB Correct.
4 Correct 27 ms 3280 KB Correct.
5 Correct 26 ms 3380 KB Correct.
6 Correct 29 ms 9128 KB Correct.
7 Correct 36 ms 9044 KB Correct.
8 Correct 26 ms 15556 KB Correct.
9 Correct 25 ms 2772 KB Correct.
10 Correct 25 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3284 KB Correct.
2 Correct 30 ms 3356 KB Correct.
3 Correct 27 ms 3412 KB Correct.
4 Correct 27 ms 2772 KB Correct.
5 Correct 27 ms 2784 KB Correct.
6 Correct 9 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 40716 KB Correct.
2 Correct 138 ms 3284 KB Correct.
3 Correct 119 ms 3392 KB Correct.
4 Correct 131 ms 3276 KB Correct.
5 Correct 84 ms 2764 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3460 KB Correct.
2 Correct 27 ms 3420 KB Correct.
3 Correct 26 ms 3420 KB Correct.
4 Correct 28 ms 9164 KB Correct.
5 Correct 22 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Correct.
2 Correct 23 ms 3412 KB Correct.
3 Correct 68 ms 52196 KB Correct.
4 Correct 21 ms 7464 KB Correct.
5 Correct 36 ms 2772 KB Correct.
6 Correct 24 ms 3436 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 3432 KB Correct.
2 Correct 24 ms 3916 KB Correct.
3 Correct 658 ms 65084 KB Correct.
4 Correct 357 ms 16912 KB Correct.
5 Correct 592 ms 29192 KB Correct.
6 Correct 206 ms 12972 KB Correct.
7 Correct 326 ms 18268 KB Correct.
8 Correct 242 ms 4964 KB Correct.
9 Correct 123 ms 3384 KB Correct.
10 Correct 132 ms 3368 KB Correct.
11 Correct 220 ms 3752 KB Correct.
12 Correct 137 ms 3352 KB Correct.
13 Correct 134 ms 3360 KB Correct.
14 Correct 337 ms 33140 KB Correct.
15 Correct 254 ms 10928 KB Correct.
16 Correct 125 ms 3424 KB Correct.
17 Correct 159 ms 3440 KB Correct.
18 Correct 144 ms 3404 KB Correct.
19 Correct 434 ms 3372 KB Correct.
20 Correct 9 ms 2644 KB Correct.
21 Correct 14 ms 3260 KB Correct.
22 Correct 16 ms 3668 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 3336 KB Correct.
2 Correct 45 ms 3796 KB Correct.
3 Correct 704 ms 67624 KB Correct.
4 Correct 333 ms 6864 KB Correct.
5 Correct 1484 ms 29200 KB Correct.
6 Correct 436 ms 12924 KB Correct.
7 Correct 619 ms 26348 KB Correct.
8 Correct 295 ms 3776 KB Correct.
9 Correct 258 ms 3460 KB Correct.
10 Correct 231 ms 3468 KB Correct.
11 Correct 131 ms 2920 KB Correct.
12 Correct 259 ms 3448 KB Correct.
13 Correct 256 ms 3460 KB Correct.
14 Correct 1389 ms 29168 KB Correct.
15 Correct 1372 ms 35188 KB Correct.
16 Correct 481 ms 14412 KB Correct.
17 Correct 331 ms 5044 KB Correct.
18 Correct 258 ms 3332 KB Correct.
19 Correct 310 ms 3500 KB Correct.
20 Correct 290 ms 3412 KB Correct.
21 Correct 905 ms 3464 KB Correct.
22 Correct 13 ms 2644 KB Correct.
23 Correct 21 ms 3256 KB Correct.
24 Correct 32 ms 3688 KB Correct.