oj.uz

Submission #751894

# Submission time Handle Problem Language Result Execution time Memory
751894 2023-06-01T17:35:35 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92912 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] = 1e14;
        }
    }
    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 = 1e14;
    // 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 21 ms 2772 KB Correct.
2 Correct 22 ms 2780 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3336 KB Correct.
2 Correct 26 ms 3340 KB Correct.
3 Correct 25 ms 3340 KB Correct.
4 Correct 28 ms 3336 KB Correct.
5 Correct 27 ms 3284 KB Correct.
6 Correct 27 ms 8660 KB Correct.
7 Correct 33 ms 8500 KB Correct.
8 Correct 18 ms 14572 KB Correct.
9 Correct 24 ms 2776 KB Correct.
10 Correct 24 ms 2784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3232 KB Correct.
2 Correct 30 ms 3328 KB Correct.
3 Correct 31 ms 3372 KB Correct.
4 Correct 29 ms 2800 KB Correct.
5 Correct 28 ms 2772 KB Correct.
6 Correct 9 ms 7636 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 40252 KB Correct.
2 Correct 248 ms 3520 KB Correct.
3 Correct 180 ms 3568 KB Correct.
4 Correct 188 ms 3492 KB Correct.
5 Correct 161 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3412 KB Correct.
2 Correct 30 ms 3348 KB Correct.
3 Correct 24 ms 3412 KB Correct.
4 Correct 28 ms 8796 KB Correct.
5 Correct 21 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 21 ms 3424 KB Correct.
3 Correct 60 ms 48500 KB Correct.
4 Correct 19 ms 7124 KB Correct.
5 Correct 28 ms 2776 KB Correct.
6 Correct 24 ms 3408 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 3840 KB Correct.
2 Correct 30 ms 4652 KB Correct.
3 Correct 689 ms 62772 KB Correct.
4 Correct 549 ms 16624 KB Correct.
5 Correct 728 ms 59996 KB Correct.
6 Correct 391 ms 28884 KB Correct.
7 Correct 513 ms 17780 KB Correct.
8 Correct 476 ms 5012 KB Correct.
9 Correct 167 ms 4188 KB Correct.
10 Correct 163 ms 4228 KB Correct.
11 Correct 485 ms 3896 KB Correct.
12 Correct 209 ms 4208 KB Correct.
13 Correct 205 ms 4168 KB Correct.
14 Correct 455 ms 32264 KB Correct.
15 Correct 512 ms 11008 KB Correct.
16 Correct 162 ms 4076 KB Correct.
17 Correct 204 ms 4008 KB Correct.
18 Correct 191 ms 3864 KB Correct.
19 Correct 423 ms 3808 KB Correct.
20 Correct 15 ms 2900 KB Correct.
21 Correct 14 ms 3580 KB Correct.
22 Correct 29 ms 5728 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 5444 KB Correct.
2 Correct 89 ms 6812 KB Correct.
3 Correct 619 ms 65888 KB Correct.
4 Correct 1103 ms 8200 KB Correct.
5 Correct 2555 ms 92912 KB Correct.
6 Correct 1400 ms 78192 KB Correct.
7 Correct 1230 ms 29388 KB Correct.
8 Correct 1242 ms 4644 KB Correct.
9 Correct 595 ms 6532 KB Correct.
10 Correct 590 ms 6952 KB Correct.
11 Execution timed out 3059 ms 3100 KB Time limit exceeded
12 Halted 0 ms 0 KB -