oj.uz

Submission #751898

# Submission time Handle Problem Language Result Execution time Memory
751898 2023-06-01T17:39:28 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92496 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] = 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)});
            }
        }
    }
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j <= k; j++)
    //     {
    //         cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << "\n";
    //     }
    // }
    double ans = dist[h][0];
    for(int i = 1; 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 22 ms 2844 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3352 KB Correct.
2 Correct 25 ms 3344 KB Correct.
3 Correct 27 ms 3316 KB Correct.
4 Correct 27 ms 3344 KB Correct.
5 Correct 25 ms 3308 KB Correct.
6 Correct 25 ms 8580 KB Correct.
7 Correct 30 ms 8404 KB Correct.
8 Correct 19 ms 14420 KB Correct.
9 Correct 23 ms 2792 KB Correct.
10 Correct 22 ms 2792 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3284 KB Correct.
2 Correct 26 ms 3320 KB Correct.
3 Correct 25 ms 3340 KB Correct.
4 Correct 28 ms 2792 KB Correct.
5 Correct 28 ms 2772 KB Correct.
6 Correct 8 ms 7508 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 39812 KB Correct.
2 Correct 197 ms 3504 KB Correct.
3 Correct 169 ms 3564 KB Correct.
4 Correct 187 ms 3732 KB Correct.
5 Correct 164 ms 2836 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3412 KB Correct.
2 Correct 23 ms 3388 KB Correct.
3 Correct 26 ms 3412 KB Correct.
4 Correct 27 ms 8708 KB Correct.
5 Correct 26 ms 2900 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 3412 KB Correct.
3 Correct 54 ms 47932 KB Correct.
4 Correct 20 ms 7104 KB Correct.
5 Correct 23 ms 2772 KB Correct.
6 Correct 23 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 3952 KB Correct.
2 Correct 30 ms 4636 KB Correct.
3 Correct 790 ms 61904 KB Correct.
4 Correct 512 ms 16412 KB Correct.
5 Correct 788 ms 59676 KB Correct.
6 Correct 393 ms 28768 KB Correct.
7 Correct 495 ms 17608 KB Correct.
8 Correct 480 ms 5132 KB Correct.
9 Correct 177 ms 4160 KB Correct.
10 Correct 163 ms 4168 KB Correct.
11 Correct 462 ms 4020 KB Correct.
12 Correct 179 ms 4208 KB Correct.
13 Correct 206 ms 4276 KB Correct.
14 Correct 467 ms 31912 KB Correct.
15 Correct 500 ms 11064 KB Correct.
16 Correct 164 ms 4092 KB Correct.
17 Correct 208 ms 4008 KB Correct.
18 Correct 194 ms 3932 KB Correct.
19 Correct 431 ms 3768 KB Correct.
20 Correct 15 ms 2900 KB Correct.
21 Correct 14 ms 3580 KB Correct.
22 Correct 35 ms 5772 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 5336 KB Correct.
2 Correct 99 ms 6800 KB Correct.
3 Correct 604 ms 65116 KB Correct.
4 Correct 1080 ms 8240 KB Correct.
5 Correct 2496 ms 92496 KB Correct.
6 Correct 1385 ms 78072 KB Correct.
7 Correct 1169 ms 29080 KB Correct.
8 Correct 1262 ms 4748 KB Correct.
9 Correct 568 ms 6420 KB Correct.
10 Correct 594 ms 7048 KB Correct.
11 Execution timed out 3065 ms 2880 KB Time limit exceeded
12 Halted 0 ms 0 KB -