oj.uz

Submission #751880

# Submission time Handle Problem Language Result Execution time Memory
751880 2023-06-01T17:23:36 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95088 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 70;
double dist[N][K];
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(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, 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[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;
            if(dist[to][cur_k] > dist[node][cur_k] + wt)
            {
                dist[to][cur_k] = dist[node][cur_k] + wt;
                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) / 2.0)
            {
                dist[to][cur_k + 1] = (dist[node][cur_k] + wt) / 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 21 ms 2800 KB Correct.
2 Correct 22 ms 2756 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3356 KB Correct.
2 Correct 27 ms 3412 KB Correct.
3 Correct 25 ms 3356 KB Correct.
4 Correct 28 ms 3392 KB Correct.
5 Correct 26 ms 3372 KB Correct.
6 Correct 30 ms 9044 KB Correct.
7 Correct 34 ms 8900 KB Correct.
8 Correct 20 ms 15140 KB Correct.
9 Correct 27 ms 2772 KB Correct.
10 Correct 26 ms 2808 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3360 KB Correct.
2 Correct 28 ms 3416 KB Correct.
3 Correct 29 ms 3452 KB Correct.
4 Correct 29 ms 2800 KB Correct.
5 Correct 34 ms 2796 KB Correct.
6 Correct 10 ms 7872 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 42052 KB Correct.
2 Correct 247 ms 3560 KB Correct.
3 Correct 174 ms 3568 KB Correct.
4 Correct 176 ms 3532 KB Correct.
5 Correct 158 ms 2828 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3540 KB Correct.
2 Correct 23 ms 3440 KB Correct.
3 Correct 23 ms 3448 KB Correct.
4 Correct 27 ms 9428 KB Correct.
5 Correct 20 ms 2812 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3500 KB Correct.
2 Correct 21 ms 3412 KB Correct.
3 Correct 58 ms 51000 KB Correct.
4 Correct 18 ms 7564 KB Correct.
5 Correct 23 ms 2772 KB Correct.
6 Correct 24 ms 3452 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3892 KB Correct.
2 Correct 30 ms 4752 KB Correct.
3 Correct 664 ms 65588 KB Correct.
4 Correct 512 ms 17504 KB Correct.
5 Correct 794 ms 62312 KB Correct.
6 Correct 404 ms 30828 KB Correct.
7 Correct 497 ms 18612 KB Correct.
8 Correct 476 ms 5244 KB Correct.
9 Correct 167 ms 4256 KB Correct.
10 Correct 157 ms 4292 KB Correct.
11 Correct 461 ms 3892 KB Correct.
12 Correct 175 ms 4312 KB Correct.
13 Correct 201 ms 4384 KB Correct.
14 Correct 447 ms 34048 KB Correct.
15 Correct 483 ms 11428 KB Correct.
16 Correct 160 ms 4184 KB Correct.
17 Correct 200 ms 4060 KB Correct.
18 Correct 188 ms 4000 KB Correct.
19 Correct 411 ms 3872 KB Correct.
20 Correct 14 ms 2892 KB Correct.
21 Correct 14 ms 3640 KB Correct.
22 Correct 29 ms 5968 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 6600 KB Correct.
2 Correct 94 ms 6888 KB Correct.
3 Correct 675 ms 69112 KB Correct.
4 Correct 1109 ms 8664 KB Correct.
5 Correct 2694 ms 95088 KB Correct.
6 Correct 1478 ms 80244 KB Correct.
7 Correct 1329 ms 30636 KB Correct.
8 Correct 1394 ms 4672 KB Correct.
9 Correct 647 ms 6660 KB Correct.
10 Correct 707 ms 7076 KB Correct.
11 Execution timed out 3063 ms 2876 KB Time limit exceeded
12 Halted 0 ms 0 KB -