oj.uz

Submission #749377

# Submission time Handle Problem Language Result Execution time Memory
749377 2023-05-27T20:29:09 Z boyliguanhan Cyberland (APIO23_cyberland) C++17
100 / 100
 2579 ms 167760 KB 
#include "cyberland.h"
#pragma GCC optimize(2)
#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 2756 KB Correct.
2 Correct 22 ms 2844 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4324 KB Correct.
2 Correct 29 ms 4368 KB Correct.
3 Correct 30 ms 4356 KB Correct.
4 Correct 29 ms 4356 KB Correct.
5 Correct 29 ms 4308 KB Correct.
6 Correct 37 ms 18672 KB Correct.
7 Correct 43 ms 18376 KB Correct.
8 Correct 29 ms 34700 KB Correct.
9 Correct 26 ms 2900 KB Correct.
10 Correct 26 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4308 KB Correct.
2 Correct 36 ms 4376 KB Correct.
3 Correct 32 ms 4432 KB Correct.
4 Correct 31 ms 2772 KB Correct.
5 Correct 34 ms 2880 KB Correct.
6 Correct 13 ms 16084 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 98316 KB Correct.
2 Correct 168 ms 4348 KB Correct.
3 Correct 148 ms 4388 KB Correct.
4 Correct 156 ms 4296 KB Correct.
5 Correct 102 ms 2868 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4436 KB Correct.
2 Correct 27 ms 4308 KB Correct.
3 Correct 26 ms 4308 KB Correct.
4 Correct 35 ms 18732 KB Correct.
5 Correct 24 ms 2872 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4392 KB Correct.
2 Correct 25 ms 4436 KB Correct.
3 Correct 84 ms 126252 KB Correct.
4 Correct 27 ms 14372 KB Correct.
5 Correct 27 ms 2884 KB Correct.
6 Correct 27 ms 4396 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4392 KB Correct.
2 Correct 29 ms 5460 KB Correct.
3 Correct 743 ms 158352 KB Correct.
4 Correct 327 ms 38076 KB Correct.
5 Correct 790 ms 65088 KB Correct.
6 Correct 336 ms 23672 KB Correct.
7 Correct 331 ms 41500 KB Correct.
8 Correct 246 ms 8436 KB Correct.
9 Correct 135 ms 4468 KB Correct.
10 Correct 122 ms 4424 KB Correct.
11 Correct 236 ms 4832 KB Correct.
12 Correct 157 ms 4472 KB Correct.
13 Correct 152 ms 4448 KB Correct.
14 Correct 347 ms 78720 KB Correct.
15 Correct 271 ms 23112 KB Correct.
16 Correct 142 ms 4432 KB Correct.
17 Correct 175 ms 4452 KB Correct.
18 Correct 152 ms 4420 KB Correct.
19 Correct 388 ms 4476 KB Correct.
20 Correct 10 ms 2772 KB Correct.
21 Correct 13 ms 4264 KB Correct.
22 Correct 23 ms 4564 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 4556 KB Correct.
2 Correct 79 ms 5520 KB Correct.
3 Correct 1282 ms 167760 KB Correct.
4 Correct 383 ms 13016 KB Correct.
5 Correct 2579 ms 65060 KB Correct.
6 Correct 1020 ms 23680 KB Correct.
7 Correct 783 ms 61052 KB Correct.
8 Correct 405 ms 5164 KB Correct.
9 Correct 387 ms 4460 KB Correct.
10 Correct 340 ms 4512 KB Correct.
11 Correct 223 ms 2936 KB Correct.
12 Correct 451 ms 4556 KB Correct.
13 Correct 437 ms 4444 KB Correct.
14 Correct 2146 ms 67072 KB Correct.
15 Correct 1674 ms 83500 KB Correct.
16 Correct 527 ms 31656 KB Correct.
17 Correct 416 ms 8604 KB Correct.
18 Correct 393 ms 4428 KB Correct.
19 Correct 502 ms 4552 KB Correct.
20 Correct 432 ms 4428 KB Correct.
21 Correct 1172 ms 4592 KB Correct.
22 Correct 21 ms 2772 KB Correct.
23 Correct 31 ms 4128 KB Correct.
24 Correct 63 ms 4564 KB Correct.