Submission #933534

#	Time	Username	Problem	Language	Result	Execution time	Memory
933534		JuanJL	Cyberland (APIO23_cyberland)	C++17	97 / 100	3008 ms	97104 KiB

cyberland

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
 
#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef int ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;
 
ll n,m,k,h;
vector<pll> adj[(ll)1e5+5];
ll type[(ll)1e5+5];
bool disp[(ll)1e5+5];
 
void dfs(ll nd){
	if(disp[nd]) return;
	disp[nd]=1;
	if(nd==h) return;
	for(auto i:adj[nd]) dfs(i.fst);
}
 
double Dijkstra(){
	vector<vector<double>> dist(n+5,vector<double>(k+1,-1));
	priority_queue<pair<double,pair<ll,ll>>> pq;
	pq.push({0,{0,0}});
	forn(i,0,k+1) dist[0][i]=0;
	forn(i,0,n){
		if(type[i]==0&&disp[i]){
			pq.push({0,{i,0}});
			dist[i][0]=0;
			//forn(j,0,k+1) dist[i][j]=0;
		}
	}
	double cost;
	ll nd;
	ll p2;
	ll ndV;
	double nCost;
	while(!pq.empty()){
		cost = pq.top().fst*-1;
		nd = pq.top().snd.fst;
		p2 = pq.top().snd.snd;
		pq.pop();
		if(cost>dist[nd][p2]) continue;
		
		if(nd==h) continue;
		
		for(auto i:adj[nd]){
			ndV = i.fst;
			nCost = i.snd+cost;
			if(type[ndV]==0) continue;
			if(nCost<dist[ndV][p2]||dist[ndV][p2]==-1){
				dist[ndV][p2]=nCost;
				pq.push({dist[ndV][p2]*-1,{ndV,p2}});
			}
			if(type[ndV]==2&&p2+1<min((ll)k+1,(ll)k+1)){
				nCost/=2;
				if(nCost<dist[ndV][p2+1]||dist[ndV][p2+1]==-1){
					dist[ndV][p2+1]=nCost;
					pq.push({dist[ndV][p2+1]*-1,{ndV,p2+1}});					
				}
			}
		}
	}
	double res = -1;
	forn(i,0,k+1) if(dist[h][i]!=-1&&(res>dist[h][i]||res==-1))  res = dist[h][i];
	return (double)res;
}	
 
 
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
	n=N;m=M;k=min((ll)K,(ll)70);h=H;	
	forn(i,0,n) disp[i]=0,adj[i].clear(),type[i]=arr[i];
	forn(i,0,SZ(x))	adj[x[i]].pb({y[i],c[i]}),adj[y[i]].pb({x[i],c[i]});
	dfs(0);
	return Dijkstra();
}

• 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: 0 / 3