oj.uz

Submission #749376

# Submission time Handle Problem Language Result Execution time Memory
749376 2023-05-27T20:24:51 Z boyliguanhan Cyberland (APIO23_cyberland) C++17
100 / 100
 2593 ms 167692 KB 
#include "cyberland.h"
#define go(a,b,c,d) if(dis[a][b][c]>d) dis[a][b][c] = d, pq.push({b, {d, a, c}});
#include <bits/stdc++.h>
using namespace std;
double dis[100000][100][2], ans;
bool vis[100000];
vector<pair<int, int>> adj[100000];
void dfs(int n, int h) {
    if(vis[n]) return;
    vis[n] = 1;
    if(n==h) return;
    for(auto i: adj[n])
        dfs(i.first, h);
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 100);
    arr[0] = 0, ans = 1e18;
    for(int i = 0; i < N; i++)
        for(auto &j: dis[i])
            j[0] = j[1] = 1e18;
    for(int i = 0; i < N; i++)
        adj[i].clear(), vis[i] = 0;
    for(int i = 0; i < M; i++)
        adj[x[i]].push_back({y[i], c[i]}), adj[y[i]].push_back({x[i], c[i]});
    dfs(0, H);
    if(!vis[H]) return -1;
    priority_queue<pair<int, tuple<double, int, int>>, vector<pair<int, tuple<double, int, int>>>, greater<>> pq;
    for(int i = 0; i < N; i++)
        if(vis[i]&&!arr[i])
            pq.push({0, {0, i, 0}});
    while(pq.size()) {
        double dist;
        int node, halves, halved;
        tie(dist, node, halved) = pq.top().second;
        halves = pq.top().first, pq.pop();
        if(node==H) {ans = min(ans, dist); continue;}
        if(!halved&&halves<K&&arr[node] == 2) go(node, halves+1, 1, dist/2);
        for(auto i: adj[node])
            go(i.first, halves, 0, dist+i.second);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2712 KB Correct.
2 Correct 22 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4332 KB Correct.
2 Correct 34 ms 4368 KB Correct.
3 Correct 28 ms 4308 KB Correct.
4 Correct 30 ms 4348 KB Correct.
5 Correct 29 ms 4328 KB Correct.
6 Correct 34 ms 18644 KB Correct.
7 Correct 43 ms 18456 KB Correct.
8 Correct 28 ms 34772 KB Correct.
9 Correct 26 ms 2888 KB Correct.
10 Correct 28 ms 2864 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4340 KB Correct.
2 Correct 36 ms 4388 KB Correct.
3 Correct 31 ms 4436 KB Correct.
4 Correct 32 ms 2772 KB Correct.
5 Correct 33 ms 2772 KB Correct.
6 Correct 14 ms 16100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 98276 KB Correct.
2 Correct 177 ms 4324 KB Correct.
3 Correct 148 ms 4396 KB Correct.
4 Correct 168 ms 4360 KB Correct.
5 Correct 107 ms 2856 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4320 KB Correct.
2 Correct 28 ms 4436 KB Correct.
3 Correct 26 ms 4356 KB Correct.
4 Correct 36 ms 18708 KB Correct.
5 Correct 23 ms 2876 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4436 KB Correct.
2 Correct 25 ms 4436 KB Correct.
3 Correct 86 ms 126292 KB Correct.
4 Correct 27 ms 14384 KB Correct.
5 Correct 27 ms 2880 KB Correct.
6 Correct 28 ms 4436 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4392 KB Correct.
2 Correct 30 ms 5544 KB Correct.
3 Correct 722 ms 158276 KB Correct.
4 Correct 346 ms 38048 KB Correct.
5 Correct 839 ms 65000 KB Correct.
6 Correct 342 ms 23752 KB Correct.
7 Correct 331 ms 41552 KB Correct.
8 Correct 244 ms 8652 KB Correct.
9 Correct 135 ms 4400 KB Correct.
10 Correct 123 ms 4372 KB Correct.
11 Correct 235 ms 4956 KB Correct.
12 Correct 152 ms 4432 KB Correct.
13 Correct 148 ms 4456 KB Correct.
14 Correct 371 ms 78672 KB Correct.
15 Correct 276 ms 23128 KB Correct.
16 Correct 143 ms 4444 KB Correct.
17 Correct 176 ms 4448 KB Correct.
18 Correct 151 ms 4484 KB Correct.
19 Correct 383 ms 4360 KB Correct.
20 Correct 10 ms 2852 KB Correct.
21 Correct 13 ms 4264 KB Correct.
22 Correct 22 ms 4652 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 4448 KB Correct.
2 Correct 75 ms 5460 KB Correct.
3 Correct 1286 ms 167692 KB Correct.
4 Correct 386 ms 13068 KB Correct.
5 Correct 2593 ms 65100 KB Correct.
6 Correct 1037 ms 23740 KB Correct.
7 Correct 787 ms 61016 KB Correct.
8 Correct 403 ms 5188 KB Correct.
9 Correct 389 ms 4584 KB Correct.
10 Correct 344 ms 4456 KB Correct.
11 Correct 224 ms 2844 KB Correct.
12 Correct 445 ms 4692 KB Correct.
13 Correct 454 ms 4376 KB Correct.
14 Correct 2029 ms 67016 KB Correct.
15 Correct 1693 ms 83516 KB Correct.
16 Correct 541 ms 31756 KB Correct.
17 Correct 421 ms 8480 KB Correct.
18 Correct 391 ms 4528 KB Correct.
19 Correct 490 ms 4352 KB Correct.
20 Correct 430 ms 4508 KB Correct.
21 Correct 1157 ms 4624 KB Correct.
22 Correct 20 ms 2772 KB Correct.
23 Correct 30 ms 4180 KB Correct.
24 Correct 61 ms 4552 KB Correct.