oj.uz

Submission #924911

# Submission time Handle Problem Language Result Execution time Memory
924911 2024-02-10T04:10:26 Z pan Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 22144 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long 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;
vector<pd> adj[100005];
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(80, 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 2047 ms 5132 KB Correct.
2 Correct 2072 ms 5380 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5336 KB Correct.
2 Correct 61 ms 5212 KB Correct.
3 Correct 59 ms 5212 KB Correct.
4 Correct 66 ms 5212 KB Correct.
5 Correct 65 ms 5560 KB Correct.
6 Correct 28 ms 6732 KB Correct.
7 Correct 38 ms 6592 KB Correct.
8 Correct 15 ms 8232 KB Correct.
9 Correct 286 ms 5200 KB Correct.
10 Correct 225 ms 5208 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5304 KB Correct.
2 Correct 61 ms 5208 KB Correct.
3 Correct 66 ms 5516 KB Correct.
4 Correct 246 ms 5208 KB Correct.
5 Correct 287 ms 5212 KB Correct.
6 Correct 9 ms 6488 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13956 KB Correct.
2 Correct 171 ms 5208 KB Correct.
3 Correct 154 ms 5384 KB Correct.
4 Correct 163 ms 5208 KB Correct.
5 Correct 292 ms 5208 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5380 KB Correct.
2 Correct 50 ms 5208 KB Correct.
3 Correct 50 ms 5208 KB Correct.
4 Correct 28 ms 6492 KB Correct.
5 Correct 224 ms 5220 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5208 KB Correct.
2 Correct 47 ms 5208 KB Correct.
3 Correct 45 ms 16872 KB Correct.
4 Correct 20 ms 6476 KB Correct.
5 Correct 228 ms 5212 KB Correct.
6 Correct 48 ms 5252 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 5208 KB Correct.
2 Correct 29 ms 5468 KB Correct.
3 Correct 603 ms 22144 KB Correct.
4 Correct 369 ms 10568 KB Correct.
5 Correct 605 ms 20424 KB Correct.
6 Correct 289 ms 17948 KB Correct.
7 Correct 379 ms 9856 KB Correct.
8 Correct 358 ms 7648 KB Correct.
9 Correct 164 ms 6220 KB Correct.
10 Correct 163 ms 6200 KB Correct.
11 Correct 405 ms 7312 KB Correct.
12 Correct 179 ms 6228 KB Correct.
13 Correct 179 ms 6316 KB Correct.
14 Correct 339 ms 14144 KB Correct.
15 Correct 355 ms 8948 KB Correct.
16 Correct 176 ms 6224 KB Correct.
17 Correct 200 ms 6232 KB Correct.
18 Correct 196 ms 6228 KB Correct.
19 Correct 479 ms 7116 KB Correct.
20 Correct 31 ms 5408 KB Correct.
21 Correct 15 ms 5208 KB Correct.
22 Correct 24 ms 6492 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 5380 KB Correct.
2 Correct 64 ms 5468 KB Correct.
3 Correct 340 ms 21812 KB Correct.
4 Correct 457 ms 8104 KB Correct.
5 Correct 1610 ms 20712 KB Correct.
6 Correct 693 ms 18192 KB Correct.
7 Correct 728 ms 13352 KB Correct.
8 Correct 530 ms 7252 KB Correct.
9 Correct 340 ms 6224 KB Correct.
10 Correct 344 ms 6248 KB Correct.
11 Execution timed out 3052 ms 6532 KB Time limit exceeded
12 Halted 0 ms 0 KB -