oj.uz

답안 #924916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924916 2024-02-10T04:17:08 Z pan 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 12352 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 1755 ms 3104 KB Correct.
2 Correct 1754 ms 3176 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -