Submission #749204

#	Time	Username	Problem	Language	Result	Execution time	Memory
749204		kshitij_sodani	Cyberland (APIO23_cyberland)	C++17	100 / 100	2767 ms	176928 KiB

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3