Submission #984754

#	Time	Username	Problem	Language	Result	Execution time	Memory
984754		MuhammadSaram	Cyberland (APIO23_cyberland)	C++17	0 / 100	29 ms	6976 KiB

cyberland

/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* Prophet Muhammad صلى الله عليه وسلم ************/
   /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/

#ifdef ONLINE_JUDGE
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#else

#endif

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define in binary_search
#define ll long long
#define ld long double
#define Hey ios::sync_with_stdio(false);
#define Welcome cin.tie(NULL), cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()

const int M = 1e5 + 1;
const double inf = 1e15;

vector<pair<int,int>> nei[M];

double dijkstra(int h,vector<int> a)
{
	int n=a.size();
	double dis[n];
	dis[0]=0;
	for (int i=1;i<n;i++)
		dis[i]=inf;
	set<pair<int,int>> se;
	se.insert({0,0});
	while (!se.empty())
	{
		auto x=*se.begin();
		int u=x.second,d=x.first;
		se.erase(x);
		if (u==h)
			continue;
		for (auto i:nei[u])
			if (dis[i.first]>(double)(d+i.second)*a[i.first])
			{
				se.erase({dis[i.first],i.first});
				dis[i.first]=(double)(d+i.second)*a[i.first];
				se.insert({dis[i.first],i.first});
			}
	}
	if (dis[h]==inf)
		dis[h]=-1;
	return dis[h];
}

double solve(int N,int m,int k,int H,vector<int> x,vector<int> y,vector<int> c,vector<int> a)
{
	for (int i=0;i<N;i++)
		nei[i].clear();
	for (int i=0;i<m;i++)
	{
		nei[x[i]].push_back({y[i],c[i]});
		nei[y[i]].push_back({x[i],c[i]});
	}
	return dijkstra(H,a);
}

• 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