Submission #749946

#	Time	Username	Problem	Language	Result	Execution time	Memory
749946		jamezzz	Cyberland (APIO23_cyberland)	C++17	100 / 100	1484 ms	67624 KiB

cyberland

#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 / 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