oj.uz

Submission #751884

# Submission time Handle Problem Language Result Execution time Memory
751884 2023-06-01T17:27:40 Z aryan12 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93144 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 69;
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, 68);
    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;
            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 = 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 22 ms 2772 KB Correct.
2 Correct 24 ms 2856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3292 KB Correct.
2 Correct 27 ms 3312 KB Correct.
3 Correct 24 ms 3308 KB Correct.
4 Correct 28 ms 3284 KB Correct.
5 Correct 26 ms 3284 KB Correct.
6 Correct 25 ms 8676 KB Correct.
7 Correct 31 ms 8584 KB Correct.
8 Correct 18 ms 14752 KB Correct.
9 Correct 27 ms 2916 KB Correct.
10 Correct 23 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3324 KB Correct.
2 Correct 27 ms 3284 KB Correct.
3 Correct 26 ms 3324 KB Correct.
4 Correct 26 ms 2796 KB Correct.
5 Correct 26 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 174 ms 40696 KB Correct.
2 Correct 199 ms 3500 KB Correct.
3 Correct 174 ms 3564 KB Correct.
4 Correct 180 ms 3520 KB Correct.
5 Correct 172 ms 2836 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 24 ms 3400 KB Correct.
3 Correct 24 ms 3412 KB Correct.
4 Correct 27 ms 8832 KB Correct.
5 Correct 22 ms 2780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3372 KB Correct.
2 Correct 21 ms 3412 KB Correct.
3 Correct 59 ms 49100 KB Correct.
4 Correct 21 ms 7252 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 24 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3880 KB Correct.
2 Correct 30 ms 4652 KB Correct.
3 Correct 689 ms 63404 KB Correct.
4 Correct 518 ms 16840 KB Correct.
5 Correct 770 ms 60244 KB Correct.
6 Correct 372 ms 28948 KB Correct.
7 Correct 493 ms 18040 KB Correct.
8 Correct 472 ms 5048 KB Correct.
9 Correct 169 ms 4112 KB Correct.
10 Correct 156 ms 4264 KB Correct.
11 Correct 459 ms 3764 KB Correct.
12 Correct 178 ms 4204 KB Correct.
13 Correct 194 ms 4148 KB Correct.
14 Correct 438 ms 32792 KB Correct.
15 Correct 486 ms 11100 KB Correct.
16 Correct 165 ms 4140 KB Correct.
17 Correct 202 ms 3988 KB Correct.
18 Correct 182 ms 3848 KB Correct.
19 Correct 412 ms 3924 KB Correct.
20 Correct 15 ms 2900 KB Correct.
21 Correct 14 ms 3636 KB Correct.
22 Correct 29 ms 5832 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 6632 KB Correct.
2 Correct 90 ms 6760 KB Correct.
3 Correct 643 ms 66672 KB Correct.
4 Correct 1052 ms 8284 KB Correct.
5 Correct 2610 ms 93144 KB Correct.
6 Correct 1396 ms 78268 KB Correct.
7 Correct 1192 ms 29704 KB Correct.
8 Correct 1251 ms 4776 KB Correct.
9 Correct 591 ms 6508 KB Correct.
10 Correct 553 ms 6864 KB Correct.
11 Execution timed out 3057 ms 3108 KB Time limit exceeded
12 Halted 0 ms 0 KB -