oj.uz

Submission #749892

# Submission time Handle Problem Language Result Execution time Memory
749892 2023-05-28T20:52:15 Z Cyber_Wolf Cyberland (APIO23_cyberland) C++17
100 / 100
 2561 ms 177224 KB 
#include "cyberland.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#include <vector>
#pragma GCC optimize("Ofast")
#define lg long long
#define ld long double
#define ff first
#define sf second
using namespace std;

const lg N = 1e5+5, K = 71;

ld dist[N][K];
lg in_queue[N][K];
vector<array<lg, 2>> adj[N];


double solve(int n, int m, int k, int h, std::vector<int> g, std::vector<int> r, std::vector<int> d, std::vector<int> t) 
{
k = min(k, 70);
	for(int i = 0; i < n; i++)	adj[i].clear();
    for(int i = 0; i < m; i++)
    {
    	adj[g[i]].push_back({r[i], d[i]});
    	adj[r[i]].push_back({g[i], d[i]});
    }
	adj[h].clear();
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j <= k; j++)
    	{
    		dist[i][j] = 1e18;
    		in_queue[i][j] = 0;
    	}
    }
    dist[0][k] = 0;
    priority_queue<pair<ld, lg>> pq[71];
    pq[k].push({-dist[0][k], 0});
    in_queue[0][k] = 1;
    for(int i = k; i >= 0; i--)
    {
	    while(pq[i].size())
	    {
	    	pair<ld, lg> p = pq[i].top();
	    	pq[i].pop();
	    	in_queue[p.sf][i] = 0;
	    	for(auto [it, c] : adj[p.sf])
	    	{
	    		ld cost = dist[p.sf][i]+c;
	    		if(t[it] == 0)	cost = 0;
	    		if(t[it] == 2 && i > 0 && dist[it][i-1] > (cost)/2.0)
	    		{
	    			dist[it][i-1] = cost/2.0;
	    			if(!in_queue[it][i-1])pq[i-1].push({-dist[it][i-1], it});
	    			in_queue[it][i-1] = true;
	    		}
	    		if(dist[it][i] > cost)
	    		{
	    			dist[it][i] = cost;
	    			if(!in_queue[it][i])pq[i].push({-dist[it][i], it});
	    			in_queue[it][i] = true;
	    		}
	    	}
	    }
    }
    ld ans = 1e18;
    for(int i = 0; i <= k; i++)
    {
    	ans = min(ans, dist[h][i]);
    }
    if(ans > 1e15)
    {
    	ans = -1;	
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2772 KB Correct.
2 Correct 34 ms 2768 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4596 KB Correct.
2 Correct 38 ms 4436 KB Correct.
3 Correct 37 ms 4520 KB Correct.
4 Correct 38 ms 4492 KB Correct.
5 Correct 38 ms 4468 KB Correct.
6 Correct 48 ms 19900 KB Correct.
7 Correct 58 ms 19588 KB Correct.
8 Correct 37 ms 37068 KB Correct.
9 Correct 34 ms 2880 KB Correct.
10 Correct 34 ms 2904 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4556 KB Correct.
2 Correct 38 ms 4464 KB Correct.
3 Correct 35 ms 4436 KB Correct.
4 Correct 39 ms 2892 KB Correct.
5 Correct 39 ms 2912 KB Correct.
6 Correct 15 ms 16724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 108920 KB Correct.
2 Correct 170 ms 4872 KB Correct.
3 Correct 150 ms 4932 KB Correct.
4 Correct 159 ms 4792 KB Correct.
5 Correct 113 ms 2952 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4548 KB Correct.
2 Correct 34 ms 4600 KB Correct.
3 Correct 35 ms 4576 KB Correct.
4 Correct 42 ms 20052 KB Correct.
5 Correct 32 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4504 KB Correct.
2 Correct 32 ms 4564 KB Correct.
3 Correct 105 ms 135272 KB Correct.
4 Correct 32 ms 15188 KB Correct.
5 Correct 33 ms 2904 KB Correct.
6 Correct 34 ms 4588 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 4968 KB Correct.
2 Correct 26 ms 6244 KB Correct.
3 Correct 1056 ms 171760 KB Correct.
4 Correct 584 ms 41304 KB Correct.
5 Correct 842 ms 87304 KB Correct.
6 Correct 280 ms 33496 KB Correct.
7 Correct 560 ms 45076 KB Correct.
8 Correct 355 ms 9000 KB Correct.
9 Correct 142 ms 5084 KB Correct.
10 Correct 149 ms 4912 KB Correct.
11 Correct 320 ms 5116 KB Correct.
12 Correct 168 ms 5008 KB Correct.
13 Correct 155 ms 5060 KB Correct.
14 Correct 571 ms 84880 KB Correct.
15 Correct 429 ms 24884 KB Correct.
16 Correct 152 ms 4960 KB Correct.
17 Correct 185 ms 4988 KB Correct.
18 Correct 187 ms 5004 KB Correct.
19 Correct 492 ms 5084 KB Correct.
20 Correct 12 ms 2900 KB Correct.
21 Correct 15 ms 4448 KB Correct.
22 Correct 20 ms 5588 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 5640 KB Correct.
2 Correct 51 ms 6804 KB Correct.
3 Correct 1063 ms 177224 KB Correct.
4 Correct 538 ms 14692 KB Correct.
5 Correct 1864 ms 110692 KB Correct.
6 Correct 597 ms 43688 KB Correct.
7 Correct 1131 ms 65904 KB Correct.
8 Correct 487 ms 5744 KB Correct.
9 Correct 291 ms 5596 KB Correct.
10 Correct 302 ms 5360 KB Correct.
11 Correct 289 ms 2952 KB Correct.
12 Correct 336 ms 5448 KB Correct.
13 Correct 318 ms 5580 KB Correct.
14 Correct 2561 ms 96336 KB Correct.
15 Correct 2208 ms 93596 KB Correct.
16 Correct 947 ms 36656 KB Correct.
17 Correct 522 ms 10056 KB Correct.
18 Correct 309 ms 5460 KB Correct.
19 Correct 375 ms 5728 KB Correct.
20 Correct 357 ms 5540 KB Correct.
21 Correct 1070 ms 5648 KB Correct.
22 Correct 21 ms 3016 KB Correct.
23 Correct 31 ms 4804 KB Correct.
24 Correct 40 ms 6460 KB Correct.