oj.uz

Submission #753123

# Submission time Handle Problem Language Result Execution time Memory
753123 2023-06-04T16:23:23 Z Jarif_Rahman Cyberland (APIO23_cyberland) C++17
100 / 100
 2347 ms 23008 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef long double ld;

const long double inf = 1e18;

vector<vector<pair<int, long double>>> graph;
vector<bool> reachable;

void dfs(int nd){
    if(reachable[nd]) return;
    reachable[nd] = 1;
    for(auto [x, w]: graph[nd]) dfs(x);
}

double solve(int n, int m, int k, int h, vector<int> U, vector<int> V, vector<int> C, vector<int> arr){
    k = min(k, 70);
    k++;

    graph.assign(n, {});
    vector<pair<int, long double>> edge_with_h;
    reachable.assign(n, 0);

    for(int i = 0; i < m; i++){
        if(U[i] == h || V[i] == h){
            edge_with_h.pb({U[i]+V[i]-h, C[i]});
            continue;
        }
        graph[U[i]].pb({V[i], C[i]});
        graph[V[i]].pb({U[i], C[i]});
    }

    dfs(0);

    vector<long double> dis(n, inf);
    vector<bool> bl(n, 0);
    priority_queue
    <pair<long double, int>, vector<pair<long double, int>>, greater<pair<long double, int>>> pq;

    for(int i = 0; i < n; i++) if(i == 0 || (arr[i] == 0 && reachable[i])){
        dis[i] = 0;
    }

    for(int ki = 0; ki < k; ki++){
        if(ki != 0){
            auto _dis = dis;
            for(int i = 0; i < n; i++) if(arr[i] == 2 && reachable[i]){
                if(i == h) continue;
                for(auto [x, w]: graph[i]) dis[i] = min(dis[i], (_dis[x]+w)/ld(2));
            }
        }

        bl.assign(n, 0);
        for(int i = 0; i < n; i++) if(reachable[i]) pq.push({dis[i], i});

        while(!pq.empty()){
            int nd = pq.top().sc;
            pq.pop();
            if(bl[nd]) continue;
            bl[nd] = 1;

            for(auto [x, w]: graph[nd]) if(dis[nd]+w < dis[x]){
                dis[x] = dis[nd]+w;
                pq.push({dis[x], x});
            }
        }
    }

    long double ans = inf;
    for(auto [x, w]: edge_with_h){
        ans = min(ans, dis[x]+w);
    }

    if(ans >= inf) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 460 KB Correct.
2 Correct 36 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 628 KB Correct.
2 Correct 246 ms 744 KB Correct.
3 Correct 237 ms 688 KB Correct.
4 Correct 257 ms 692 KB Correct.
5 Correct 247 ms 636 KB Correct.
6 Correct 309 ms 2812 KB Correct.
7 Correct 397 ms 2676 KB Correct.
8 Correct 208 ms 4560 KB Correct.
9 Correct 149 ms 508 KB Correct.
10 Correct 147 ms 412 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 524 KB Correct.
2 Correct 208 ms 520 KB Correct.
3 Correct 222 ms 548 KB Correct.
4 Correct 144 ms 340 KB Correct.
5 Correct 145 ms 420 KB Correct.
6 Correct 56 ms 2228 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 10828 KB Correct.
2 Correct 144 ms 556 KB Correct.
3 Correct 130 ms 544 KB Correct.
4 Correct 148 ms 528 KB Correct.
5 Correct 103 ms 468 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 624 KB Correct.
2 Correct 111 ms 604 KB Correct.
3 Correct 124 ms 672 KB Correct.
4 Correct 163 ms 2620 KB Correct.
5 Correct 80 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 616 KB Correct.
2 Correct 100 ms 688 KB Correct.
3 Correct 73 ms 13904 KB Correct.
4 Correct 90 ms 2520 KB Correct.
5 Correct 98 ms 340 KB Correct.
6 Correct 111 ms 672 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 576 KB Correct.
2 Correct 18 ms 724 KB Correct.
3 Correct 1096 ms 20112 KB Correct.
4 Correct 795 ms 5140 KB Correct.
5 Correct 535 ms 14300 KB Correct.
6 Correct 182 ms 11464 KB Correct.
7 Correct 654 ms 5588 KB Correct.
8 Correct 507 ms 1200 KB Correct.
9 Correct 112 ms 636 KB Correct.
10 Correct 119 ms 652 KB Correct.
11 Correct 410 ms 752 KB Correct.
12 Correct 131 ms 592 KB Correct.
13 Correct 128 ms 716 KB Correct.
14 Correct 499 ms 10224 KB Correct.
15 Correct 506 ms 3068 KB Correct.
16 Correct 134 ms 652 KB Correct.
17 Correct 152 ms 700 KB Correct.
18 Correct 161 ms 664 KB Correct.
19 Correct 431 ms 728 KB Correct.
20 Correct 9 ms 340 KB Correct.
21 Correct 11 ms 468 KB Correct.
22 Correct 12 ms 1620 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 596 KB Correct.
2 Correct 37 ms 764 KB Correct.
3 Correct 2332 ms 23008 KB Correct.
4 Correct 654 ms 1864 KB Correct.
5 Correct 1141 ms 14280 KB Correct.
6 Correct 400 ms 11476 KB Correct.
7 Correct 845 ms 9708 KB Correct.
8 Correct 589 ms 952 KB Correct.
9 Correct 217 ms 704 KB Correct.
10 Correct 238 ms 772 KB Correct.
11 Correct 235 ms 524 KB Correct.
12 Correct 252 ms 600 KB Correct.
13 Correct 230 ms 712 KB Correct.
14 Correct 1773 ms 12168 KB Correct.
15 Correct 2347 ms 10420 KB Correct.
16 Correct 1065 ms 4716 KB Correct.
17 Correct 690 ms 1236 KB Correct.
18 Correct 245 ms 788 KB Correct.
19 Correct 307 ms 700 KB Correct.
20 Correct 293 ms 588 KB Correct.
21 Correct 874 ms 612 KB Correct.
22 Correct 22 ms 356 KB Correct.
23 Correct 18 ms 468 KB Correct.
24 Correct 22 ms 1620 KB Correct.