Submission #924916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924916	2024-02-10T04:17:08 Z	pan	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	12352 KB

cyberland

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ld> pd;
typedef pair<ld, ll> pd2;
typedef pair<string, ll> psi;
typedef pair<ll, ll> pi;
typedef pair<ld, pi> pdi;
const long double INF = 1e18;
struct compare
{
	bool operator() (pd2 const&  a, pd2 const&  b)
	{
		return a.f>b.f; // least element come out first
	}
};
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)
{
	ld ans = INF;
	ll n = N;
	vector<pd> adj[100005];
	for (ll i=0; i<M; ++i)
	{
		adj[x[i]].pb(mp(y[i], (ld) c[i]));
		adj[y[i]].pb(mp(x[i], (ld) c[i]));
	}
	vector<ld> dist(n+5, INF);
	priority_queue<pd2, vector<pd2>, compare> pq;
	dist[0] = 0.0; 
	pq.push(mp(0, 0));
	for (ll i=min(70, K); i>=0; --i)
	{
		priority_queue<pd2, vector<pd2>, compare> newpq;
		vector<ld> newdist(n+5, INF);
		while (pq.size())
		{
			ll city = pq.top().s;
			ld cost = pq.top().f;
			pq.pop();
			if (cost>dist[city] || city==H) continue;
			for (pd u: adj[city])
			{
				if (arr[u.f]==0 && dist[u.f]>0.0) 
				{
					dist[u.f] = 0.0;
					pq.push(mp(0.0, u.f));
				}
				ld newcost = cost  + (ld) u.s;
				if (newcost<dist[u.f]) 
				{
					dist[u.f] = newcost;
					pq.push(mp(dist[u.f], u.f));
				}
				if (arr[u.f]==2 && i>0 && (newcost)/ (ld) 2.0 < newdist[u.f])
				{
					newdist[u.f] = newcost/(ld) 2.0; 
					newpq.push(mp(newdist[u.f], u.f));
				}
 
			}
		}
		ans = min(ans, dist[H]);
		dist = newdist;
		pq = newpq;
		
	}
 
	return (ans==INF)?-1: ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1755 ms	3104 KB	Correct.
2	Correct	1754 ms	3176 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2908 KB	Correct.
2	Correct	47 ms	3156 KB	Correct.
3	Correct	42 ms	2908 KB	Correct.
4	Correct	44 ms	2924 KB	Correct.
5	Correct	42 ms	2904 KB	Correct.
6	Correct	23 ms	3624 KB	Correct.
7	Correct	30 ms	3700 KB	Correct.
8	Correct	12 ms	4800 KB	Correct.
9	Correct	205 ms	2652 KB	Correct.
10	Correct	210 ms	2652 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	2908 KB	Correct.
2	Correct	43 ms	2904 KB	Correct.
3	Correct	41 ms	2904 KB	Correct.
4	Correct	196 ms	2648 KB	Correct.
5	Correct	196 ms	2848 KB	Correct.
6	Correct	6 ms	3420 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	8636 KB	Correct.
2	Correct	114 ms	2932 KB	Correct.
3	Correct	100 ms	2908 KB	Correct.
4	Correct	112 ms	2904 KB	Correct.
5	Correct	225 ms	2848 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	2904 KB	Correct.
2	Correct	43 ms	2908 KB	Correct.
3	Correct	43 ms	2904 KB	Correct.
4	Correct	24 ms	3672 KB	Correct.
5	Correct	187 ms	2844 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	2944 KB	Correct.
2	Correct	39 ms	2908 KB	Correct.
3	Correct	46 ms	10432 KB	Correct.
4	Correct	17 ms	3676 KB	Correct.
5	Correct	190 ms	2844 KB	Correct.
6	Correct	41 ms	2904 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	2908 KB	Correct.
2	Correct	21 ms	2908 KB	Correct.
3	Correct	335 ms	12352 KB	Correct.
4	Correct	244 ms	4780 KB	Correct.
5	Correct	376 ms	10932 KB	Correct.
6	Correct	175 ms	9400 KB	Correct.
7	Correct	251 ms	5016 KB	Correct.
8	Correct	239 ms	3148 KB	Correct.
9	Correct	113 ms	2952 KB	Correct.
10	Correct	112 ms	2952 KB	Correct.
11	Correct	263 ms	3280 KB	Correct.
12	Correct	124 ms	2908 KB	Correct.
13	Correct	121 ms	2920 KB	Correct.
14	Correct	239 ms	7520 KB	Correct.
15	Correct	233 ms	4032 KB	Correct.
16	Correct	122 ms	2904 KB	Correct.
17	Correct	139 ms	3152 KB	Correct.
18	Correct	136 ms	2964 KB	Correct.
19	Correct	323 ms	2908 KB	Correct.
20	Correct	27 ms	2652 KB	Correct.
21	Correct	11 ms	2652 KB	Correct.
22	Correct	16 ms	3380 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	240 ms	2940 KB	Correct.
2	Correct	39 ms	2908 KB	Correct.
3	Correct	207 ms	12180 KB	Correct.
4	Correct	282 ms	3320 KB	Correct.
5	Correct	829 ms	11144 KB	Correct.
6	Correct	371 ms	9336 KB	Correct.
7	Correct	439 ms	6552 KB	Correct.
8	Correct	319 ms	2960 KB	Correct.
9	Correct	191 ms	2992 KB	Correct.
10	Correct	192 ms	2908 KB	Correct.
11	Execution timed out	3072 ms	3156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #924916

Compilation message