oj.uz

Submission #751895

# Submission time Handle Problem Language Result Execution time Memory
751895 2023-06-01T17:37:00 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93032 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 = dist[h][0];
    // 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 = 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 22 ms 2772 KB Correct.
2 Correct 24 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3292 KB Correct.
2 Correct 27 ms 3292 KB Correct.
3 Correct 26 ms 3340 KB Correct.
4 Correct 26 ms 3348 KB Correct.
5 Correct 26 ms 3284 KB Correct.
6 Correct 27 ms 8660 KB Correct.
7 Correct 32 ms 8496 KB Correct.
8 Correct 18 ms 14644 KB Correct.
9 Correct 25 ms 2772 KB Correct.
10 Correct 24 ms 2796 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3328 KB Correct.
2 Correct 27 ms 3340 KB Correct.
3 Correct 26 ms 3336 KB Correct.
4 Correct 26 ms 2800 KB Correct.
5 Correct 26 ms 2796 KB Correct.
6 Correct 9 ms 7652 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 40236 KB Correct.
2 Correct 201 ms 3572 KB Correct.
3 Correct 186 ms 3508 KB Correct.
4 Correct 190 ms 3516 KB Correct.
5 Correct 174 ms 2788 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3412 KB Correct.
2 Correct 24 ms 3284 KB Correct.
3 Correct 22 ms 3376 KB Correct.
4 Correct 26 ms 8756 KB Correct.
5 Correct 23 ms 2788 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3412 KB Correct.
2 Correct 22 ms 3412 KB Correct.
3 Correct 52 ms 48416 KB Correct.
4 Correct 18 ms 7124 KB Correct.
5 Correct 23 ms 2784 KB Correct.
6 Correct 23 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 3836 KB Correct.
2 Correct 29 ms 4736 KB Correct.
3 Correct 634 ms 62704 KB Correct.
4 Correct 514 ms 16648 KB Correct.
5 Correct 723 ms 59944 KB Correct.
6 Correct 383 ms 28864 KB Correct.
7 Correct 495 ms 17916 KB Correct.
8 Correct 492 ms 5092 KB Correct.
9 Correct 175 ms 4048 KB Correct.
10 Correct 156 ms 4184 KB Correct.
11 Correct 478 ms 3764 KB Correct.
12 Correct 177 ms 4204 KB Correct.
13 Correct 196 ms 4180 KB Correct.
14 Correct 450 ms 32324 KB Correct.
15 Correct 501 ms 10976 KB Correct.
16 Correct 162 ms 4076 KB Correct.
17 Correct 205 ms 4008 KB Correct.
18 Correct 186 ms 3880 KB Correct.
19 Correct 416 ms 3776 KB Correct.
20 Correct 14 ms 2900 KB Correct.
21 Correct 14 ms 3552 KB Correct.
22 Correct 33 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 5524 KB Correct.
2 Correct 90 ms 6772 KB Correct.
3 Correct 621 ms 65940 KB Correct.
4 Correct 1031 ms 8228 KB Correct.
5 Correct 2621 ms 93032 KB Correct.
6 Correct 1401 ms 78204 KB Correct.
7 Correct 1193 ms 29428 KB Correct.
8 Correct 1205 ms 4964 KB Correct.
9 Correct 588 ms 6544 KB Correct.
10 Correct 567 ms 6828 KB Correct.
11 Execution timed out 3069 ms 3124 KB Time limit exceeded
12 Halted 0 ms 0 KB -