oj.uz

Submission #749228

# Submission time Handle Problem Language Result Execution time Memory
749228 2023-05-27T14:59:51 Z b00norp Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 159592 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

const int NN = 1e5 + 5, KK = 71 ;
vector<array<int, 2> > g[NN];
bool isreachable[NN];
double dp[NN][KK];
int a[NN];

void dfs(int node, int restricted)
{
    isreachable[node] = true;
    for(auto [to, wt]: g[node])
    {
        if(to == restricted)
        {
            isreachable[restricted] = true;
        }
        if(to == restricted || isreachable[to]) continue;
        dfs(to, restricted);
    }
}

double solve(int N, int M, int K, int H, vector<int> x, 
    vector<int> y, vector<int> c, vector<int> arr) 
{
    K = min(K, 70);
    for(int i = 0; i < N; i++)
    {
        a[i] = arr[i];
        isreachable[i] = false;
        g[i].clear();
        for(int j = 0; j <= K; j++)
        {
            dp[i][j] = 1e18;
        }
    }
    for(int i = 0; i < M; i++)
    {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    dfs(0, H);
    if(!isreachable[H])
    {
        return -1;
    }
    priority_queue<pair<double, pair<int, int> > > pq;
    dp[0][0] = 0;
    pq.push({-dp[0][0], {0, 0}});
    for(int i = 1; i < N; i++)
    {
        if(isreachable[i] && arr[i] == 0)
        {
            dp[i][0] = 0;
            pq.push({-dp[i][0], {i, 0}});
        }
    }
    while(!pq.empty())
    {
        auto [dis, l] = pq.top();
        auto [node, k] = l;
        // cout << "dis = " << dis << ", node = " << node << ", k = " << k << "\n";
        pq.pop();
        dis = -dis;
        if(dp[node][k] < dis)
        {
            continue;
        }
        for(auto [to, wt]: g[node])
        {
            if(dp[to][k] > dp[node][k] + wt)
            {
                dp[to][k] = dp[node][k] + (long long)wt;
                if(to != H)
                {
                    pq.push({-dp[to][k], {to, k}});
                }
            }
            // cout << "a[to] = " << a[to] << "k = " << k << ", K = " << K << ", dp[to][k + 1] = " << dp[to][k + 1] << "\n";
            if(a[to] == 2 && k != K && dp[to][k + 1] > (dp[node][k] + (double)wt) / 2.0)
            {
                dp[to][k + 1] = (dp[node][k] + wt) / 2.0;
                if(to != H)
                {
                    pq.push({-dp[to][k + 1], {to, k + 1}});
                }
            }
        }
    }
    double ans = 1e18;
    for(int i = 0; i <= K; i++)
    {
        ans = min(ans, dp[H][i]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2840 KB Correct.
2 Correct 20 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3372 KB Correct.
2 Correct 27 ms 3336 KB Correct.
3 Correct 25 ms 3324 KB Correct.
4 Correct 26 ms 3352 KB Correct.
5 Correct 26 ms 3296 KB Correct.
6 Correct 28 ms 8828 KB Correct.
7 Correct 32 ms 8788 KB Correct.
8 Correct 19 ms 15024 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 23 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3340 KB Correct.
2 Correct 26 ms 3352 KB Correct.
3 Correct 25 ms 3396 KB Correct.
4 Correct 26 ms 2772 KB Correct.
5 Correct 26 ms 2736 KB Correct.
6 Correct 9 ms 7764 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 43784 KB Correct.
2 Correct 282 ms 3776 KB Correct.
3 Correct 240 ms 3820 KB Correct.
4 Correct 262 ms 3788 KB Correct.
5 Correct 210 ms 2988 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 24 ms 3424 KB Correct.
3 Correct 23 ms 3424 KB Correct.
4 Correct 27 ms 9020 KB Correct.
5 Correct 20 ms 2768 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 24 ms 3428 KB Correct.
3 Correct 59 ms 50216 KB Correct.
4 Correct 20 ms 7356 KB Correct.
5 Correct 24 ms 2780 KB Correct.
6 Correct 26 ms 3448 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 4292 KB Correct.
2 Correct 46 ms 5468 KB Correct.
3 Correct 719 ms 64864 KB Correct.
4 Correct 557 ms 17072 KB Correct.
5 Correct 1126 ms 61364 KB Correct.
6 Correct 523 ms 45704 KB Correct.
7 Correct 511 ms 18548 KB Correct.
8 Correct 489 ms 5128 KB Correct.
9 Correct 224 ms 4808 KB Correct.
10 Correct 205 ms 4320 KB Correct.
11 Correct 483 ms 3784 KB Correct.
12 Correct 247 ms 4384 KB Correct.
13 Correct 265 ms 4324 KB Correct.
14 Correct 437 ms 33452 KB Correct.
15 Correct 488 ms 11372 KB Correct.
16 Correct 237 ms 4304 KB Correct.
17 Correct 282 ms 4208 KB Correct.
18 Correct 250 ms 4316 KB Correct.
19 Correct 613 ms 4180 KB Correct.
20 Correct 21 ms 3156 KB Correct.
21 Correct 18 ms 3780 KB Correct.
22 Correct 39 ms 5832 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 7120 KB Correct.
2 Correct 137 ms 9908 KB Correct.
3 Correct 673 ms 69716 KB Correct.
4 Correct 1070 ms 8520 KB Correct.
5 Execution timed out 3058 ms 159592 KB Time limit exceeded
6 Halted 0 ms 0 KB -