Submission #933083

#	Time	Username	Problem	Language	Result	Execution time	Memory
933083		JuanJL	Cyberland (APIO23_cyberland)	C++17	0 / 100	33 ms	22608 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 long long 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<vector<pll>> adj;
vector<ll> type;
vector<bool> inComp;

void dfs(ll nd){
	if(inComp[nd]) return;
	inComp[nd]=1;
	if(nd==h) return;
	for(auto i:adj[nd]) dfs(i.fst);
}

double dijkstra(){
	double dist[n+1][35];
	//mset(dist,-1);// -> No funcaaa AHHHHH
	forn(i,0,n+1)forn(j,0,35) dist[i][j]=-1; // -> Este si funciona
	
	priority_queue<pair<ll,pll>> pq;
	dist[h][0]=0;
	pq.push({0,{h,0}});
	while(!pq.empty()){
		ll cost = pq.top().fst*-1;
		ll nd = pq.top().snd.fst;
		ll p2 = pq.top().snd.snd;
		pq.pop();
		//if(p2>0) cout<<"P2\n";
		if(dist[nd][p2]<cost&&dist[nd][p2]!=-1) break;
		
		for(auto i:adj[nd]){
			double newCost = i.snd;
			forn(i,0,p2) newCost/=2;
			//if(p2>0) cout<<p2<<"->"<<newCost<<'\n';;
			newCost+=cost;
			if(type[i.fst]==1){
				if(newCost<dist[i.fst][p2]||dist[i.fst][p2]==-1){
					dist[i.fst][p2]=newCost;
					pq.push({dist[i.fst][p2],{i.fst,p2}});
				}
			}else if(type[i.fst]==0){
				if(newCost<dist[i.fst][p2]||dist[i.fst][p2]==-1){
					dist[i.fst][p2]=newCost;

				}
			}else if(type[i.fst]==2){
				
				if(p2+1<35){
					
					if(newCost<dist[i.fst][p2+1]||dist[i.fst][p2+1]==-1){
						dist[i.fst][p2+1]=newCost;
						pq.push({dist[i.fst][p2+1]*-1,{i.fst,p2+1}});
						
					}			
				}else{
					if(newCost<dist[i.fst][p2]||dist[i.fst][p2]==-1){
						dist[i.fst][p2]=newCost;
						pq.push({dist[i.fst][p2]*-1,{i.fst,p2}});
					}
				}
			}
		}
	}
	double res = -1;
	type[0]=0;
	forn(i,0,n){
		if(type[i]!=0) continue;
		forn(j,0,35){
			if(dist[i][j]!=-1&&(dist[i][j]<res||res==-1)&&inComp[i]) res = dist[i][j];
		}
	}
	//cout<<res<<'\n';
	return 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=K;h=H;
	adj.clear();
	adj.resize(n);
	type.clear();
	type.resize(n);
	inComp.clear();
	inComp.resize(n,0);
	forn(i,0,SZ(x))	adj[x[i]].pb({y[i],c[i]}),adj[y[i]].pb({x[i],c[i]});
	forn(i,0,n) type[i]=arr[i];
	dfs(0);
	return dijkstra();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3