oj.uz

Submission #765388

# Submission time Handle Problem Language Result Execution time Memory
765388 2023-06-24T12:01:23 Z pandapythoner Cyberland (APIO23_cyberland) C++17
100 / 100
 2548 ms 20076 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

#define flt long double

struct edge {
    int to;
    long long cost;
};

const flt inf = 1e100;
int n, m;
vector<vector<edge>> g;

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    n = N;
    m = M;
    K = min(K, 70);
    g.assign(n, {});
    for (int i = 0; i < m; i += 1) {
        int u = x[i];
        int v = y[i];
        int cost = c[i];
        g[u].push_back({v, cost});
        g[v].push_back({u, cost});
    }
    vector<flt> dst(n, inf);
    dst[0] = 0;
    for(int iter = 0; iter <= K + 2; iter += 1){
        set<pair<flt, int>> q;
        for(int i = 0; i < n; i += 1){
            q.emplace(dst[i], i);
        }
        while(!q.empty()){
            int v = q.begin()->second;
            q.erase(q.begin());
            if(v == H){
                continue;
            }
            for(auto [to, cost]: g[v]){
                if(dst[to] > dst[v] + cost){
                    q.erase(make_pair(dst[to], to));
                    dst[to] = dst[v] + cost;
                    q.insert(make_pair(dst[to], to));
                }
            }
        }
        auto new_dst = dst;
        for(int i = 0; i < n; i += 1){
            if(dst[i] < inf / 10){
                if(arr[i] == 0){
                    new_dst[i] = 0;
                } else if(arr[i] == 2 && iter > 1 && iter != K + 2){
                    for(auto [to, cost]: g[i]){
                        new_dst[to] = min(new_dst[to], dst[i] / 2 + (flt)(cost));
                    }
                }
            }
        }
        dst = new_dst;
    }
    if(dst[H] >= inf / 10){
        return -1;
    }
    return dst[H];
}

/*
3 2 30 2
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 460 KB Correct.
2 Correct 54 ms 452 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 548 KB Correct.
2 Correct 311 ms 468 KB Correct.
3 Correct 297 ms 504 KB Correct.
4 Correct 309 ms 544 KB Correct.
5 Correct 307 ms 572 KB Correct.
6 Correct 335 ms 2252 KB Correct.
7 Correct 447 ms 2196 KB Correct.
8 Correct 210 ms 4248 KB Correct.
9 Correct 168 ms 412 KB Correct.
10 Correct 176 ms 412 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 548 KB Correct.
2 Correct 280 ms 524 KB Correct.
3 Correct 267 ms 516 KB Correct.
4 Correct 183 ms 372 KB Correct.
5 Correct 193 ms 392 KB Correct.
6 Correct 61 ms 1916 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 11856 KB Correct.
2 Correct 288 ms 496 KB Correct.
3 Correct 233 ms 500 KB Correct.
4 Correct 238 ms 468 KB Correct.
5 Correct 182 ms 404 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 480 KB Correct.
2 Correct 250 ms 584 KB Correct.
3 Correct 253 ms 604 KB Correct.
4 Correct 256 ms 2212 KB Correct.
5 Correct 164 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 500 KB Correct.
2 Correct 228 ms 556 KB Correct.
3 Correct 544 ms 15732 KB Correct.
4 Correct 207 ms 1972 KB Correct.
5 Correct 172 ms 372 KB Correct.
6 Correct 223 ms 488 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 468 KB Correct.
2 Correct 27 ms 616 KB Correct.
3 Correct 1374 ms 19388 KB Correct.
4 Correct 805 ms 4580 KB Correct.
5 Correct 481 ms 10792 KB Correct.
6 Correct 168 ms 6860 KB Correct.
7 Correct 719 ms 5016 KB Correct.
8 Correct 567 ms 1080 KB Correct.
9 Correct 237 ms 596 KB Correct.
10 Correct 244 ms 516 KB Correct.
11 Correct 495 ms 704 KB Correct.
12 Correct 280 ms 544 KB Correct.
13 Correct 253 ms 604 KB Correct.
14 Correct 650 ms 9676 KB Correct.
15 Correct 603 ms 2764 KB Correct.
16 Correct 257 ms 572 KB Correct.
17 Correct 277 ms 604 KB Correct.
18 Correct 264 ms 532 KB Correct.
19 Correct 635 ms 660 KB Correct.
20 Correct 17 ms 364 KB Correct.
21 Correct 24 ms 444 KB Correct.
22 Correct 13 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 624 KB Correct.
2 Correct 53 ms 620 KB Correct.
3 Correct 1604 ms 20076 KB Correct.
4 Correct 815 ms 1556 KB Correct.
5 Correct 1041 ms 10536 KB Correct.
6 Correct 318 ms 6876 KB Correct.
7 Correct 1040 ms 7656 KB Correct.
8 Correct 733 ms 688 KB Correct.
9 Correct 507 ms 620 KB Correct.
10 Correct 487 ms 548 KB Correct.
11 Correct 265 ms 560 KB Correct.
12 Correct 560 ms 648 KB Correct.
13 Correct 494 ms 608 KB Correct.
14 Correct 2094 ms 9772 KB Correct.
15 Correct 2548 ms 10128 KB Correct.
16 Correct 1229 ms 3840 KB Correct.
17 Correct 777 ms 1060 KB Correct.
18 Correct 510 ms 656 KB Correct.
19 Correct 569 ms 524 KB Correct.
20 Correct 539 ms 588 KB Correct.
21 Correct 1333 ms 696 KB Correct.
22 Correct 32 ms 340 KB Correct.
23 Correct 48 ms 340 KB Correct.
24 Correct 29 ms 980 KB Correct.