oj.uz

Submission #751883

# Submission time Handle Problem Language Result Execution time Memory
751883 2023-06-01T17:25:58 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 94856 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 69;
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, 68);
    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, int> > pq;
    for(int i = 0; i < n; i++)
    {
        // cout << "source[i] = " << source[i] << "\n";
        if(source[i])
        {
            pq.push({0, i});
            dist[i][0] = 0;
        }
    }
    while(!pq.empty())
    {
        auto [dis, p] = pq.top();
        pq.pop();
        int cur_k = p / 100000, node = p % 100000;
        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 + 100000 * 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 + 100000 * (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 2844 KB Correct.
2 Correct 22 ms 2784 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3372 KB Correct.
2 Correct 25 ms 3316 KB Correct.
3 Correct 24 ms 3384 KB Correct.
4 Correct 25 ms 3324 KB Correct.
5 Correct 25 ms 3388 KB Correct.
6 Correct 26 ms 8964 KB Correct.
7 Correct 32 ms 8756 KB Correct.
8 Correct 19 ms 14976 KB Correct.
9 Correct 24 ms 2796 KB Correct.
10 Correct 27 ms 2792 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3284 KB Correct.
2 Correct 26 ms 3412 KB Correct.
3 Correct 24 ms 3428 KB Correct.
4 Correct 25 ms 2796 KB Correct.
5 Correct 25 ms 2792 KB Correct.
6 Correct 9 ms 7764 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 41540 KB Correct.
2 Correct 200 ms 3620 KB Correct.
3 Correct 186 ms 3568 KB Correct.
4 Correct 179 ms 3484 KB Correct.
5 Correct 167 ms 2840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3504 KB Correct.
2 Correct 23 ms 3412 KB Correct.
3 Correct 23 ms 3484 KB Correct.
4 Correct 29 ms 9344 KB Correct.
5 Correct 21 ms 2780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 20 ms 3432 KB Correct.
3 Correct 61 ms 50380 KB Correct.
4 Correct 19 ms 7540 KB Correct.
5 Correct 22 ms 2780 KB Correct.
6 Correct 22 ms 3540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 3936 KB Correct.
2 Correct 29 ms 4740 KB Correct.
3 Correct 701 ms 64864 KB Correct.
4 Correct 529 ms 17368 KB Correct.
5 Correct 748 ms 61972 KB Correct.
6 Correct 375 ms 30800 KB Correct.
7 Correct 501 ms 18424 KB Correct.
8 Correct 488 ms 5220 KB Correct.
9 Correct 161 ms 4276 KB Correct.
10 Correct 152 ms 4288 KB Correct.
11 Correct 463 ms 3784 KB Correct.
12 Correct 181 ms 4340 KB Correct.
13 Correct 194 ms 4292 KB Correct.
14 Correct 481 ms 33784 KB Correct.
15 Correct 481 ms 11324 KB Correct.
16 Correct 160 ms 4236 KB Correct.
17 Correct 203 ms 4012 KB Correct.
18 Correct 182 ms 3948 KB Correct.
19 Correct 396 ms 3872 KB Correct.
20 Correct 14 ms 2900 KB Correct.
21 Correct 14 ms 3708 KB Correct.
22 Correct 29 ms 5968 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 6556 KB Correct.
2 Correct 89 ms 6944 KB Correct.
3 Correct 644 ms 68244 KB Correct.
4 Correct 1047 ms 8752 KB Correct.
5 Correct 2531 ms 94856 KB Correct.
6 Correct 1376 ms 79988 KB Correct.
7 Correct 1278 ms 30332 KB Correct.
8 Correct 1257 ms 4656 KB Correct.
9 Correct 602 ms 6584 KB Correct.
10 Correct 586 ms 6960 KB Correct.
11 Execution timed out 3057 ms 3128 KB Time limit exceeded
12 Halted 0 ms 0 KB -