Submission #749204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749204	2023-05-27T14:25:29 Z	kshitij_sodani	Cyberland (APIO23_cyberland)	C++17	100 / 100	2767 ms	176928 KB

cyberland

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
 
#include "cyberland.h"
 
#include <vector>
 
vector<pair<int,int>> adj[100001];
long double dist[100001][101];
bool vis[100001][101];
double solve(int n, int m, int k, int x,vector<int> aa,vector<int> bb, vector<int> cc, vector<int> it) {
	for(int i=0;i<n;i++){
		adj[i].clear();
		for(int j=0;j<=min(70,k);j++){
			dist[i][j]=-1;
			vis[i][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		adj[aa[i]].pb({bb[i],cc[i]});
		adj[bb[i]].pb({aa[i],cc[i]});
	}
	dist[0][0]=0;
	vis[0][0]=1;
	/*
	priority_queue<pair<long double,pair<int,int>>> ss;
	
	ss.push({0,{0,0}});*/
	for(int i=0;i<=min(70,k);i++){
		priority_queue<pair<long double,pair<int,int>>> ss;
 
		for(int j=0;j<n;j++){
			if(vis[j][i]==1 and j!=x){
				ss.push({-dist[j][i],{j,i}});
			}
		}
		while(ss.size()){
			pair<long double,pair<int,int>> no=ss.top();
			no.a=-no.a;
			ss.pop();
			if(dist[no.b.a][no.b.b]<no.a){
				continue;
			}
			if(no.b.a==x){
				continue;
			}
			for(auto j:adj[no.b.a]){
				long double mi=no.a+j.b;
				pair<int,int> rr={j.a,no.b.b};
				if(it[j.a]==0){
					mi=0;
				}
				if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
					dist[rr.a][rr.b]=mi;
					vis[rr.a][rr.b]=1;
					ss.push({-mi,{rr.a,rr.b}});
				}
				if(it[j.a]==2){
					mi/=(long double)2;
					rr.b+=1;
					if(rr.b>70){
						continue;
					}
					if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
						dist[rr.a][rr.b]=mi;
						vis[rr.a][rr.b]=1;
						//ss.push({-mi,{rr.a,rr.b}});
					}
				}
			}
		}
	}
 
	long double ans=-1;
	int st=0;
	for(int i=0;i<=min(k,70);i++){
		if(vis[x][i]==1){
			if(st==0){
				st=1;
				ans=dist[x][i];
			}
			if(dist[x][i]<=ans-0.0000001){
				ans=dist[x][i];
			}
		}
	}
 
 
 
 
 
 
 
	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	2772 KB	Correct.
2	Correct	26 ms	2772 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4508 KB	Correct.
2	Correct	35 ms	4452 KB	Correct.
3	Correct	32 ms	4496 KB	Correct.
4	Correct	33 ms	4460 KB	Correct.
5	Correct	32 ms	4476 KB	Correct.
6	Correct	40 ms	19868 KB	Correct.
7	Correct	48 ms	19556 KB	Correct.
8	Correct	35 ms	37076 KB	Correct.
9	Correct	29 ms	2892 KB	Correct.
10	Correct	31 ms	2900 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	4428 KB	Correct.
2	Correct	37 ms	4448 KB	Correct.
3	Correct	32 ms	4436 KB	Correct.
4	Correct	31 ms	2880 KB	Correct.
5	Correct	31 ms	2896 KB	Correct.
6	Correct	15 ms	16724 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	242 ms	104568 KB	Correct.
2	Correct	173 ms	4536 KB	Correct.
3	Correct	150 ms	4428 KB	Correct.
4	Correct	158 ms	4404 KB	Correct.
5	Correct	103 ms	2868 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	4564 KB	Correct.
2	Correct	30 ms	4504 KB	Correct.
3	Correct	30 ms	4436 KB	Correct.
4	Correct	39 ms	19768 KB	Correct.
5	Correct	28 ms	2888 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	4436 KB	Correct.
2	Correct	28 ms	4444 KB	Correct.
3	Correct	98 ms	134836 KB	Correct.
4	Correct	29 ms	14960 KB	Correct.
5	Correct	28 ms	2772 KB	Correct.
6	Correct	32 ms	4448 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	4536 KB	Correct.
2	Correct	32 ms	5684 KB	Correct.
3	Correct	1151 ms	169316 KB	Correct.
4	Correct	563 ms	40460 KB	Correct.
5	Correct	923 ms	68888 KB	Correct.
6	Correct	364 ms	24688 KB	Correct.
7	Correct	610 ms	44132 KB	Correct.
8	Correct	408 ms	8884 KB	Correct.
9	Correct	158 ms	4524 KB	Correct.
10	Correct	153 ms	4496 KB	Correct.
11	Correct	367 ms	4904 KB	Correct.
12	Correct	185 ms	4544 KB	Correct.
13	Correct	178 ms	4584 KB	Correct.
14	Correct	617 ms	83828 KB	Correct.
15	Correct	459 ms	24524 KB	Correct.
16	Correct	159 ms	4448 KB	Correct.
17	Correct	203 ms	4544 KB	Correct.
18	Correct	188 ms	4640 KB	Correct.
19	Correct	543 ms	4464 KB	Correct.
20	Correct	12 ms	2772 KB	Correct.
21	Correct	16 ms	4368 KB	Correct.
22	Correct	25 ms	4692 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	4548 KB	Correct.
2	Correct	57 ms	5708 KB	Correct.
3	Correct	952 ms	176928 KB	Correct.
4	Correct	600 ms	13684 KB	Correct.
5	Correct	2081 ms	68976 KB	Correct.
6	Correct	648 ms	24692 KB	Correct.
7	Correct	1063 ms	65088 KB	Correct.
8	Correct	510 ms	5252 KB	Correct.
9	Correct	303 ms	4704 KB	Correct.
10	Correct	316 ms	4524 KB	Correct.
11	Correct	292 ms	2980 KB	Correct.
12	Correct	340 ms	4552 KB	Correct.
13	Correct	362 ms	4636 KB	Correct.
14	Correct	2767 ms	71784 KB	Correct.
15	Correct	2367 ms	89012 KB	Correct.
16	Correct	914 ms	33748 KB	Correct.
17	Correct	591 ms	8984 KB	Correct.
18	Correct	367 ms	4564 KB	Correct.
19	Correct	395 ms	4584 KB	Correct.
20	Correct	377 ms	4428 KB	Correct.
21	Correct	1103 ms	4480 KB	Correct.
22	Correct	29 ms	2772 KB	Correct.
23	Correct	27 ms	4364 KB	Correct.
24	Correct	53 ms	4692 KB	Correct.

Submission #749204

Compilation message