Submission #749202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749202	2023-05-27T14:23:37 Z	kshitij_sodani	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	176924 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(100,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(100,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>100){
						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,100);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	27 ms	2772 KB	Correct.
2	Correct	28 ms	2772 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4436 KB	Correct.
2	Correct	36 ms	4484 KB	Correct.
3	Correct	32 ms	4512 KB	Correct.
4	Correct	34 ms	4468 KB	Correct.
5	Correct	34 ms	4436 KB	Correct.
6	Correct	39 ms	19836 KB	Correct.
7	Correct	55 ms	19532 KB	Correct.
8	Correct	32 ms	36944 KB	Correct.
9	Correct	31 ms	2912 KB	Correct.
10	Correct	29 ms	2900 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	4448 KB	Correct.
2	Correct	34 ms	4436 KB	Correct.
3	Correct	34 ms	4504 KB	Correct.
4	Correct	35 ms	2900 KB	Correct.
5	Correct	36 ms	2904 KB	Correct.
6	Correct	14 ms	16720 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	104564 KB	Correct.
2	Correct	183 ms	4488 KB	Correct.
3	Correct	144 ms	4556 KB	Correct.
4	Correct	158 ms	4408 KB	Correct.
5	Correct	103 ms	2844 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	4476 KB	Correct.
2	Correct	30 ms	4448 KB	Correct.
3	Correct	31 ms	4528 KB	Correct.
4	Correct	40 ms	19812 KB	Correct.
5	Correct	24 ms	2896 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	4480 KB	Correct.
2	Correct	26 ms	4436 KB	Correct.
3	Correct	101 ms	134832 KB	Correct.
4	Correct	31 ms	15060 KB	Correct.
5	Correct	29 ms	2876 KB	Correct.
6	Correct	31 ms	4556 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	189 ms	4556 KB	Correct.
2	Correct	30 ms	5700 KB	Correct.
3	Correct	1045 ms	169164 KB	Correct.
4	Correct	609 ms	40544 KB	Correct.
5	Correct	924 ms	68748 KB	Correct.
6	Correct	302 ms	24692 KB	Correct.
7	Correct	522 ms	44364 KB	Correct.
8	Correct	379 ms	8764 KB	Correct.
9	Correct	147 ms	4556 KB	Correct.
10	Correct	148 ms	4452 KB	Correct.
11	Correct	339 ms	4952 KB	Correct.
12	Correct	166 ms	4556 KB	Correct.
13	Correct	160 ms	4492 KB	Correct.
14	Correct	553 ms	83912 KB	Correct.
15	Correct	436 ms	24428 KB	Correct.
16	Correct	157 ms	4452 KB	Correct.
17	Correct	191 ms	4560 KB	Correct.
18	Correct	185 ms	4412 KB	Correct.
19	Correct	503 ms	4492 KB	Correct.
20	Correct	12 ms	2860 KB	Correct.
21	Correct	15 ms	4312 KB	Correct.
22	Correct	22 ms	4700 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	540 ms	4548 KB	Correct.
2	Correct	74 ms	5708 KB	Correct.
3	Correct	1352 ms	176924 KB	Correct.
4	Correct	597 ms	13680 KB	Correct.
5	Correct	2791 ms	68912 KB	Correct.
6	Correct	961 ms	24864 KB	Correct.
7	Correct	1267 ms	65200 KB	Correct.
8	Correct	574 ms	5260 KB	Correct.
9	Correct	464 ms	4572 KB	Correct.
10	Correct	441 ms	4656 KB	Correct.
11	Correct	374 ms	3060 KB	Correct.
12	Correct	473 ms	4576 KB	Correct.
13	Correct	474 ms	4560 KB	Correct.
14	Execution timed out	3037 ms	71456 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Submission #749202

Compilation message