oj.uz

Submission #751891

# Submission time Handle Problem Language Result Execution time Memory
751891 2023-06-01T17:33:59 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92532 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 67;
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, 66);
    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 23 ms 2756 KB Correct.
2 Correct 23 ms 2812 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3284 KB Correct.
2 Correct 31 ms 3300 KB Correct.
3 Correct 28 ms 3328 KB Correct.
4 Correct 28 ms 3340 KB Correct.
5 Correct 35 ms 3284 KB Correct.
6 Correct 41 ms 8576 KB Correct.
7 Correct 38 ms 8404 KB Correct.
8 Correct 26 ms 14420 KB Correct.
9 Correct 25 ms 2776 KB Correct.
10 Correct 26 ms 2792 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3304 KB Correct.
2 Correct 32 ms 3284 KB Correct.
3 Correct 36 ms 3284 KB Correct.
4 Correct 36 ms 2796 KB Correct.
5 Correct 47 ms 2784 KB Correct.
6 Correct 13 ms 7620 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 39804 KB Correct.
2 Correct 252 ms 3504 KB Correct.
3 Correct 205 ms 3484 KB Correct.
4 Correct 271 ms 3480 KB Correct.
5 Correct 204 ms 2844 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3380 KB Correct.
2 Correct 31 ms 3344 KB Correct.
3 Correct 31 ms 3368 KB Correct.
4 Correct 40 ms 8684 KB Correct.
5 Correct 23 ms 2780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3396 KB Correct.
2 Correct 29 ms 3340 KB Correct.
3 Correct 70 ms 47852 KB Correct.
4 Correct 21 ms 7072 KB Correct.
5 Correct 30 ms 2788 KB Correct.
6 Correct 26 ms 3424 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 3904 KB Correct.
2 Correct 41 ms 4624 KB Correct.
3 Correct 822 ms 61960 KB Correct.
4 Correct 610 ms 16388 KB Correct.
5 Correct 891 ms 59796 KB Correct.
6 Correct 435 ms 28844 KB Correct.
7 Correct 570 ms 17684 KB Correct.
8 Correct 545 ms 5096 KB Correct.
9 Correct 178 ms 4060 KB Correct.
10 Correct 174 ms 4252 KB Correct.
11 Correct 540 ms 3808 KB Correct.
12 Correct 205 ms 4188 KB Correct.
13 Correct 237 ms 4140 KB Correct.
14 Correct 514 ms 31916 KB Correct.
15 Correct 553 ms 10860 KB Correct.
16 Correct 183 ms 4128 KB Correct.
17 Correct 230 ms 3996 KB Correct.
18 Correct 210 ms 3832 KB Correct.
19 Correct 492 ms 3760 KB Correct.
20 Correct 15 ms 2884 KB Correct.
21 Correct 17 ms 3624 KB Correct.
22 Correct 36 ms 5720 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 5300 KB Correct.
2 Correct 108 ms 6788 KB Correct.
3 Correct 708 ms 65108 KB Correct.
4 Correct 1174 ms 8140 KB Correct.
5 Correct 2767 ms 92532 KB Correct.
6 Correct 1508 ms 78092 KB Correct.
7 Correct 1262 ms 29040 KB Correct.
8 Correct 1312 ms 4584 KB Correct.
9 Correct 657 ms 6468 KB Correct.
10 Correct 599 ms 6900 KB Correct.
11 Execution timed out 3026 ms 2916 KB Time limit exceeded
12 Halted 0 ms 0 KB -