oj.uz

Submission #751868

# Submission time Handle Problem Language Result Execution time Memory
751868 2023-06-01T17:12:01 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 128416 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 2756 KB Correct.
2 Correct 21 ms 2732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Correct.
2 Correct 26 ms 3392 KB Correct.
3 Correct 24 ms 3312 KB Correct.
4 Correct 26 ms 3412 KB Correct.
5 Correct 27 ms 3400 KB Correct.
6 Correct 25 ms 9196 KB Correct.
7 Correct 33 ms 9044 KB Correct.
8 Correct 19 ms 15444 KB Correct.
9 Correct 23 ms 2784 KB Correct.
10 Correct 23 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3384 KB Correct.
2 Correct 32 ms 3348 KB Correct.
3 Correct 26 ms 3412 KB Correct.
4 Correct 28 ms 2772 KB Correct.
5 Correct 27 ms 2776 KB Correct.
6 Correct 9 ms 8020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 43736 KB Correct.
2 Correct 226 ms 3968 KB Correct.
3 Correct 198 ms 3676 KB Correct.
4 Correct 217 ms 3656 KB Correct.
5 Correct 195 ms 2980 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3540 KB Correct.
2 Correct 25 ms 3524 KB Correct.
3 Correct 25 ms 3412 KB Correct.
4 Correct 27 ms 9484 KB Correct.
5 Correct 21 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3532 KB Correct.
2 Correct 22 ms 3540 KB Correct.
3 Correct 58 ms 51892 KB Correct.
4 Correct 19 ms 7720 KB Correct.
5 Correct 29 ms 2800 KB Correct.
6 Correct 47 ms 3536 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4200 KB Correct.
2 Correct 34 ms 5232 KB Correct.
3 Correct 854 ms 67732 KB Correct.
4 Correct 622 ms 18084 KB Correct.
5 Correct 993 ms 79076 KB Correct.
6 Correct 475 ms 39224 KB Correct.
7 Correct 532 ms 19276 KB Correct.
8 Correct 495 ms 5412 KB Correct.
9 Correct 178 ms 4764 KB Correct.
10 Correct 167 ms 4744 KB Correct.
11 Correct 490 ms 3876 KB Correct.
12 Correct 202 ms 4772 KB Correct.
13 Correct 208 ms 4656 KB Correct.
14 Correct 465 ms 35556 KB Correct.
15 Correct 513 ms 11932 KB Correct.
16 Correct 187 ms 4656 KB Correct.
17 Correct 215 ms 4436 KB Correct.
18 Correct 203 ms 4208 KB Correct.
19 Correct 449 ms 4128 KB Correct.
20 Correct 16 ms 3032 KB Correct.
21 Correct 17 ms 3820 KB Correct.
22 Correct 32 ms 6988 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 8392 KB Correct.
2 Correct 106 ms 8468 KB Correct.
3 Correct 741 ms 70292 KB Correct.
4 Correct 1191 ms 9692 KB Correct.
5 Execution timed out 3055 ms 128416 KB Time limit exceeded
6 Halted 0 ms 0 KB -