oj.uz

Submission #751876

# Submission time Handle Problem Language Result Execution time Memory
751876 2023-06-01T17:18:35 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95424 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
// #define int long long
using namespace std;

const int N = 1e5 + 1, K = 70;
double dist[K][N];
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(int32_t n, int32_t m, int32_t k, int32_t h, 
    vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, 
    vector<int32_t> arr) 
{
    H = h;
    k = min(k, 69);
    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[j][i] = 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, pair<int, int> > > pq;
    for(int i = 0; i < n; i++)
    {
        // cout << "source[i] = " << source[i] << "\n";
        if(source[i])
        {
            pq.push({0, {i, 0}});
            dist[0][i] = 0;
        }
    }
    while(!pq.empty())
    {
        auto [dis, p] = pq.top();
        auto [node, cur_k] = p;
        pq.pop();
        dis = -dis;
        if(dist[cur_k][node] < dis || node == h)
        {
            continue;
        }
        for(auto [to, wt]: g[node])
        {
            if(a[to] == 0) continue;
            if(dist[cur_k][to] > dist[cur_k][node] + wt)
            {
                dist[cur_k][to] = dist[cur_k][node] + wt;
                pq.push({-dist[cur_k][to], {to, cur_k}});
            }
            if(a[to] == 1 || cur_k == k) continue;
            if(dist[cur_k + 1][to] > (dist[cur_k][node] + wt) / 2.0)
            {
                dist[cur_k + 1][to] = (dist[cur_k][node] + wt) / 2.0;
                pq.push({-dist[cur_k + 1][to], {to, 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[i][h]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2900 KB Correct.
2 Correct 22 ms 2900 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3268 KB Correct.
2 Correct 26 ms 3256 KB Correct.
3 Correct 24 ms 3276 KB Correct.
4 Correct 25 ms 3156 KB Correct.
5 Correct 25 ms 3256 KB Correct.
6 Correct 25 ms 6228 KB Correct.
7 Correct 29 ms 6148 KB Correct.
8 Correct 15 ms 9368 KB Correct.
9 Correct 23 ms 2900 KB Correct.
10 Correct 22 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3248 KB Correct.
2 Correct 26 ms 3252 KB Correct.
3 Correct 31 ms 3300 KB Correct.
4 Correct 26 ms 2924 KB Correct.
5 Correct 27 ms 2916 KB Correct.
6 Correct 8 ms 5588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 24432 KB Correct.
2 Correct 219 ms 3560 KB Correct.
3 Correct 177 ms 3568 KB Correct.
4 Correct 185 ms 3332 KB Correct.
5 Correct 167 ms 2940 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3284 KB Correct.
2 Correct 27 ms 3284 KB Correct.
3 Correct 23 ms 3348 KB Correct.
4 Correct 27 ms 6556 KB Correct.
5 Correct 21 ms 2920 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3368 KB Correct.
2 Correct 21 ms 3396 KB Correct.
3 Correct 48 ms 28088 KB Correct.
4 Correct 20 ms 5688 KB Correct.
5 Correct 23 ms 2924 KB Correct.
6 Correct 23 ms 3328 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 3836 KB Correct.
2 Correct 30 ms 4376 KB Correct.
3 Correct 736 ms 27044 KB Correct.
4 Correct 510 ms 9824 KB Correct.
5 Correct 880 ms 51476 KB Correct.
6 Correct 408 ms 27820 KB Correct.
7 Correct 475 ms 9592 KB Correct.
8 Correct 463 ms 4328 KB Correct.
9 Correct 167 ms 4036 KB Correct.
10 Correct 165 ms 4284 KB Correct.
11 Correct 456 ms 3644 KB Correct.
12 Correct 179 ms 4180 KB Correct.
13 Correct 197 ms 4188 KB Correct.
14 Correct 420 ms 13872 KB Correct.
15 Correct 504 ms 6572 KB Correct.
16 Correct 165 ms 4112 KB Correct.
17 Correct 200 ms 3976 KB Correct.
18 Correct 180 ms 3816 KB Correct.
19 Correct 399 ms 3696 KB Correct.
20 Correct 14 ms 3028 KB Correct.
21 Correct 14 ms 3540 KB Correct.
22 Correct 30 ms 5840 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 6836 KB Correct.
2 Correct 92 ms 7268 KB Correct.
3 Correct 568 ms 69024 KB Correct.
4 Correct 1088 ms 8240 KB Correct.
5 Execution timed out 3042 ms 95424 KB Time limit exceeded
6 Halted 0 ms 0 KB -