oj.uz

Submission #751874

# Submission time Handle Problem Language Result Execution time Memory
751874 2023-06-01T17:15:13 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95388 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
// #define int long long
using namespace std;

const int N = 1e5 + 5, K = 71;
double dist[N][K];
vector<pair<int, double> > g[N];
bool vis[N], source[N];
int a[N], H;

void dfs(int node)
{
    vis[node] = true;
    if(a[node] == 0)
    {
        source[node] = true;
    }
    if(node == H)
    {
        return;
    }
    for(auto [to, wt]: g[node])
    {
        if(!vis[to])
        {
            dfs(to);
        }
    }
}

double solve(int32_t n, int32_t m, int32_t k, int32_t h, 
    vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, 
    vector<int32_t> arr) 
{
    H = h;
    k = min(k, 70);
    for(int i = 0; i <= n; i++)
    {
        source[i] = false;
        vis[i] = false;
        if(i != n) a[i] = arr[i];
        g[i].clear();
        for(int j = 0; j <= k; j++)
        {
            dist[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);
    source[0] = true;
    if(!vis[H])
    {
        return -1;
    }
    priority_queue<pair<double, pair<int, int> > > pq;
    for(int i = 0; i < n; i++)
    {
        // cout << "source[i] = " << source[i] << "\n";
        if(source[i])
        {
            pq.push({0, {i, 0}});
            dist[i][0] = 0;
        }
    }
    while(!pq.empty())
    {
        auto [dis, p] = pq.top();
        auto [node, cur_k] = p;
        pq.pop();
        dis = -dis;
        if(dist[node][cur_k] < dis || node == h)
        {
            continue;
        }
        for(auto [to, wt]: g[node])
        {
            if(a[to] == 0) continue;
            if(dist[to][cur_k] > dist[node][cur_k] + wt)
            {
                dist[to][cur_k] = dist[node][cur_k] + wt;
                pq.push({-dist[to][cur_k], {to, cur_k}});
            }
            if(a[to] == 1 || cur_k == k) continue;
            if(dist[to][cur_k + 1] > (dist[node][cur_k] + wt) / 2.0)
            {
                dist[to][cur_k + 1] = (dist[node][cur_k] + wt) / 2.0;
                pq.push({-dist[to][cur_k + 1], {to, cur_k + 1}});
            }
        }
    }
    double ans = 1e18;
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j <= k; j++)
    //     {
    //         cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << "\n";
    //     }
    // }
    for(int i = 0; i <= k; i++)
    {
        ans = min(ans, dist[h][i]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2840 KB Correct.
2 Correct 23 ms 2752 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 27 ms 3440 KB Correct.
3 Correct 26 ms 3432 KB Correct.
4 Correct 26 ms 3412 KB Correct.
5 Correct 26 ms 3396 KB Correct.
6 Correct 40 ms 9032 KB Correct.
7 Correct 36 ms 8916 KB Correct.
8 Correct 19 ms 15316 KB Correct.
9 Correct 25 ms 2772 KB Correct.
10 Correct 25 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3388 KB Correct.
2 Correct 28 ms 3420 KB Correct.
3 Correct 31 ms 3412 KB Correct.
4 Correct 27 ms 2784 KB Correct.
5 Correct 26 ms 2804 KB Correct.
6 Correct 9 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 42564 KB Correct.
2 Correct 216 ms 3580 KB Correct.
3 Correct 187 ms 3688 KB Correct.
4 Correct 203 ms 3580 KB Correct.
5 Correct 177 ms 2840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3512 KB Correct.
2 Correct 27 ms 3592 KB Correct.
3 Correct 23 ms 3464 KB Correct.
4 Correct 29 ms 9540 KB Correct.
5 Correct 22 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3540 KB Correct.
2 Correct 21 ms 3540 KB Correct.
3 Correct 59 ms 51636 KB Correct.
4 Correct 19 ms 7648 KB Correct.
5 Correct 25 ms 2792 KB Correct.
6 Correct 28 ms 3456 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3904 KB Correct.
2 Correct 31 ms 4864 KB Correct.
3 Correct 737 ms 66492 KB Correct.
4 Correct 544 ms 17772 KB Correct.
5 Correct 808 ms 62568 KB Correct.
6 Correct 390 ms 30960 KB Correct.
7 Correct 521 ms 18776 KB Correct.
8 Correct 500 ms 5268 KB Correct.
9 Correct 174 ms 4312 KB Correct.
10 Correct 161 ms 4308 KB Correct.
11 Correct 464 ms 3916 KB Correct.
12 Correct 181 ms 4300 KB Correct.
13 Correct 192 ms 4256 KB Correct.
14 Correct 466 ms 34476 KB Correct.
15 Correct 494 ms 11548 KB Correct.
16 Correct 169 ms 4296 KB Correct.
17 Correct 202 ms 4040 KB Correct.
18 Correct 187 ms 3996 KB Correct.
19 Correct 442 ms 4068 KB Correct.
20 Correct 15 ms 2900 KB Correct.
21 Correct 14 ms 3708 KB Correct.
22 Correct 30 ms 6020 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 6652 KB Correct.
2 Correct 99 ms 6940 KB Correct.
3 Correct 678 ms 69812 KB Correct.
4 Correct 1101 ms 8632 KB Correct.
5 Correct 2718 ms 95388 KB Correct.
6 Correct 1524 ms 80216 KB Correct.
7 Correct 1260 ms 30856 KB Correct.
8 Correct 1321 ms 4708 KB Correct.
9 Correct 631 ms 7660 KB Correct.
10 Correct 601 ms 7432 KB Correct.
11 Execution timed out 3066 ms 2840 KB Time limit exceeded
12 Halted 0 ms 0 KB -