oj.uz

Submission #751885

# Submission time Handle Problem Language Result Execution time Memory
751885 2023-06-01T17:28:37 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92784 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 68;
double dist[N][K];
vector<pair<int, int> > 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, 67);
    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;
            double wt_d = wt;
            if(dist[to][cur_k] > dist[node][cur_k] + wt_d)
            {
                dist[to][cur_k] = dist[node][cur_k] + wt_d;
                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_d) / 2.0)
            {
                dist[to][cur_k + 1] = (dist[node][cur_k] + wt_d) / 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 20 ms 2772 KB Correct.
2 Correct 21 ms 2840 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3284 KB Correct.
2 Correct 26 ms 3296 KB Correct.
3 Correct 34 ms 3344 KB Correct.
4 Correct 29 ms 3332 KB Correct.
5 Correct 26 ms 3356 KB Correct.
6 Correct 24 ms 8616 KB Correct.
7 Correct 32 ms 8524 KB Correct.
8 Correct 18 ms 14580 KB Correct.
9 Correct 33 ms 2796 KB Correct.
10 Correct 24 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3332 KB Correct.
2 Correct 27 ms 3264 KB Correct.
3 Correct 26 ms 3388 KB Correct.
4 Correct 28 ms 2772 KB Correct.
5 Correct 25 ms 2784 KB Correct.
6 Correct 8 ms 7636 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 40164 KB Correct.
2 Correct 200 ms 3512 KB Correct.
3 Correct 188 ms 3512 KB Correct.
4 Correct 180 ms 3496 KB Correct.
5 Correct 165 ms 2800 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3412 KB Correct.
2 Correct 24 ms 3328 KB Correct.
3 Correct 23 ms 3388 KB Correct.
4 Correct 27 ms 8788 KB Correct.
5 Correct 23 ms 2776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3404 KB Correct.
2 Correct 21 ms 3412 KB Correct.
3 Correct 57 ms 48472 KB Correct.
4 Correct 18 ms 7184 KB Correct.
5 Correct 25 ms 2784 KB Correct.
6 Correct 23 ms 3508 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 3816 KB Correct.
2 Correct 29 ms 4636 KB Correct.
3 Correct 662 ms 62676 KB Correct.
4 Correct 506 ms 16556 KB Correct.
5 Correct 770 ms 60008 KB Correct.
6 Correct 376 ms 28940 KB Correct.
7 Correct 488 ms 17892 KB Correct.
8 Correct 465 ms 5072 KB Correct.
9 Correct 170 ms 4100 KB Correct.
10 Correct 191 ms 4192 KB Correct.
11 Correct 476 ms 3724 KB Correct.
12 Correct 188 ms 4236 KB Correct.
13 Correct 200 ms 4140 KB Correct.
14 Correct 431 ms 32228 KB Correct.
15 Correct 475 ms 11180 KB Correct.
16 Correct 161 ms 4080 KB Correct.
17 Correct 207 ms 3996 KB Correct.
18 Correct 185 ms 3884 KB Correct.
19 Correct 423 ms 3816 KB Correct.
20 Correct 16 ms 2900 KB Correct.
21 Correct 14 ms 3596 KB Correct.
22 Correct 31 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 5372 KB Correct.
2 Correct 90 ms 6836 KB Correct.
3 Correct 658 ms 65896 KB Correct.
4 Correct 1065 ms 8316 KB Correct.
5 Correct 2512 ms 92784 KB Correct.
6 Correct 1366 ms 78256 KB Correct.
7 Correct 1168 ms 29512 KB Correct.
8 Correct 1257 ms 4828 KB Correct.
9 Correct 584 ms 6412 KB Correct.
10 Correct 568 ms 6816 KB Correct.
11 Execution timed out 3058 ms 2912 KB Time limit exceeded
12 Halted 0 ms 0 KB -