oj.uz

Submission #751878

# Submission time Handle Problem Language Result Execution time Memory
751878 2023-06-01T17:20:33 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95128 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 70;
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(int n, int m, int k, int h, 
    vector<int> x, vector<int> y, vector<int> c, 
    vector<int> arr) 
{
    H = h;
    k = min(k, 69);
    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 23 ms 2772 KB Correct.
2 Correct 21 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 26 ms 3412 KB Correct.
3 Correct 25 ms 3400 KB Correct.
4 Correct 26 ms 3412 KB Correct.
5 Correct 29 ms 3424 KB Correct.
6 Correct 27 ms 8976 KB Correct.
7 Correct 32 ms 8900 KB Correct.
8 Correct 18 ms 15140 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 28 ms 3376 KB Correct.
2 Correct 27 ms 3400 KB Correct.
3 Correct 26 ms 3352 KB Correct.
4 Correct 27 ms 2784 KB Correct.
5 Correct 28 ms 2812 KB Correct.
6 Correct 9 ms 7816 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 42116 KB Correct.
2 Correct 226 ms 3568 KB Correct.
3 Correct 193 ms 3592 KB Correct.
4 Correct 188 ms 3540 KB Correct.
5 Correct 177 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3472 KB Correct.
2 Correct 24 ms 3448 KB Correct.
3 Correct 27 ms 3472 KB Correct.
4 Correct 28 ms 9436 KB Correct.
5 Correct 22 ms 2808 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3488 KB Correct.
2 Correct 21 ms 3456 KB Correct.
3 Correct 57 ms 51056 KB Correct.
4 Correct 19 ms 7636 KB Correct.
5 Correct 24 ms 2812 KB Correct.
6 Correct 23 ms 3456 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 3884 KB Correct.
2 Correct 29 ms 4760 KB Correct.
3 Correct 719 ms 65652 KB Correct.
4 Correct 518 ms 17520 KB Correct.
5 Correct 885 ms 62204 KB Correct.
6 Correct 405 ms 30932 KB Correct.
7 Correct 495 ms 18612 KB Correct.
8 Correct 467 ms 5400 KB Correct.
9 Correct 167 ms 4216 KB Correct.
10 Correct 158 ms 4308 KB Correct.
11 Correct 465 ms 3788 KB Correct.
12 Correct 179 ms 4308 KB Correct.
13 Correct 194 ms 4272 KB Correct.
14 Correct 438 ms 34100 KB Correct.
15 Correct 498 ms 11504 KB Correct.
16 Correct 160 ms 4220 KB Correct.
17 Correct 210 ms 4040 KB Correct.
18 Correct 192 ms 3968 KB Correct.
19 Correct 405 ms 3820 KB Correct.
20 Correct 14 ms 2900 KB Correct.
21 Correct 13 ms 3644 KB Correct.
22 Correct 30 ms 5968 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 6516 KB Correct.
2 Correct 96 ms 6916 KB Correct.
3 Correct 658 ms 69024 KB Correct.
4 Correct 1101 ms 8712 KB Correct.
5 Correct 2650 ms 95128 KB Correct.
6 Correct 1446 ms 80116 KB Correct.
7 Correct 1265 ms 30692 KB Correct.
8 Correct 1275 ms 4820 KB Correct.
9 Correct 617 ms 6748 KB Correct.
10 Correct 586 ms 6980 KB Correct.
11 Execution timed out 3067 ms 2980 KB Time limit exceeded
12 Halted 0 ms 0 KB -