oj.uz

Submission #749891

# Submission time Handle Problem Language Result Execution time Memory
749891 2023-05-28T20:48:20 Z Cyber_Wolf Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 177240 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.first
#define ss second.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, pair<lg, lg>>> pq;
    pq.push({-dist[0][k], {0, k}});
    in_queue[0][k] = 1;
    while(pq.size())
    {
    	pair<ld, pair<lg, lg>> p = pq.top();
    	pq.pop();
    	in_queue[p.sf][p.ss] = 0;
    	for(auto [it, c] : adj[p.sf])
    	{
    		ld cost = dist[p.sf][p.ss]+c;
    		if(t[it] == 0)	cost = 0;
    		if(t[it] == 2 && p.ss > 0 && dist[it][p.ss-1] > (cost)/2.0)
    		{
    			dist[it][p.ss-1] = cost/2.0;
    			if(!in_queue[it][p.ss-1])pq.push({-dist[it][p.ss-1], {it,  p.ss-1}});
    			in_queue[it][p.ss-1] = true;
    		}
    		if(dist[it][p.ss] > cost)
    		{
    			dist[it][p.ss] = cost;
    			if(!in_queue[it][p.ss])pq.push({-dist[it][p.ss], {it,  p.ss}});
    			in_queue[it][p.ss] = 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 30 ms 2772 KB Correct.
2 Correct 31 ms 2804 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4564 KB Correct.
2 Correct 38 ms 4448 KB Correct.
3 Correct 35 ms 4480 KB Correct.
4 Correct 37 ms 4464 KB Correct.
5 Correct 38 ms 4464 KB Correct.
6 Correct 43 ms 19940 KB Correct.
7 Correct 54 ms 19600 KB Correct.
8 Correct 37 ms 37064 KB Correct.
9 Correct 35 ms 2892 KB Correct.
10 Correct 35 ms 2912 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4436 KB Correct.
2 Correct 37 ms 4436 KB Correct.
3 Correct 37 ms 4420 KB Correct.
4 Correct 35 ms 2888 KB Correct.
5 Correct 35 ms 2892 KB Correct.
6 Correct 17 ms 16724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 104468 KB Correct.
2 Correct 641 ms 4528 KB Correct.
3 Correct 547 ms 4492 KB Correct.
4 Correct 567 ms 4456 KB Correct.
5 Correct 355 ms 3000 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4564 KB Correct.
2 Correct 33 ms 4608 KB Correct.
3 Correct 34 ms 4524 KB Correct.
4 Correct 42 ms 20048 KB Correct.
5 Correct 30 ms 2888 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4564 KB Correct.
2 Correct 30 ms 4540 KB Correct.
3 Correct 102 ms 135220 KB Correct.
4 Correct 33 ms 15068 KB Correct.
5 Correct 32 ms 2788 KB Correct.
6 Correct 32 ms 4564 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 5064 KB Correct.
2 Correct 36 ms 6476 KB Correct.
3 Correct 2198 ms 170160 KB Correct.
4 Correct 1539 ms 40856 KB Correct.
5 Correct 831 ms 84684 KB Correct.
6 Correct 365 ms 33756 KB Correct.
7 Correct 1420 ms 44544 KB Correct.
8 Correct 1201 ms 9072 KB Correct.
9 Correct 250 ms 5156 KB Correct.
10 Correct 263 ms 5076 KB Correct.
11 Correct 1111 ms 5040 KB Correct.
12 Correct 289 ms 5044 KB Correct.
13 Correct 267 ms 5096 KB Correct.
14 Correct 1451 ms 84620 KB Correct.
15 Correct 1494 ms 24952 KB Correct.
16 Correct 263 ms 4984 KB Correct.
17 Correct 339 ms 5120 KB Correct.
18 Correct 313 ms 5100 KB Correct.
19 Correct 882 ms 5116 KB Correct.
20 Correct 24 ms 2900 KB Correct.
21 Correct 25 ms 4612 KB Correct.
22 Correct 26 ms 5844 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 5572 KB Correct.
2 Correct 78 ms 7360 KB Correct.
3 Correct 1389 ms 177240 KB Correct.
4 Execution timed out 3071 ms 14100 KB Time limit exceeded
5 Halted 0 ms 0 KB -