oj.uz

Submission #976041

# Submission time Handle Problem Language Result Execution time Memory
976041 2024-05-06T05:53:56 Z nnin Cyberland (APIO23_cyberland) C++17
100 / 100
 1262 ms 18356 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pid pair<int,double>
#define f first
#define s second
#define A pair<double, int>

vector<pid> adj[100005];
bool reach[100005];
int HH, N;

void dfs(int u) {
    reach[u] = 1;
    if(u==HH) return;
    for(auto [v, w]:adj[u]) {
        if(!reach[v]) dfs(v);
    }
}

double mindis[100005];

void dij(vector<int> &arr) {
    priority_queue<A, vector<A>, greater<A>> pq;
    for(int i=0;i<N;i++) {
        if(reach[i] && mindis[i]<1e18) pq.push({mindis[i], i});
    }
    vector<bool> vis(N, 0);
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        if(u==HH) continue;
        for(auto [v, w]:adj[u]) {
            if(reach[v] && !vis[v] && mindis[v]>mindis[u]+w) {
                mindis[v] = mindis[u]+w;
                pq.push({mindis[v], v});
            }
        }
    }
    vector<pid> tmp;
    for(int u=0;u<N;u++) {
        double mn = mindis[u];
        if(reach[u] && arr[u]==2) {
            for(auto [v, w]:adj[u]) {
                if(reach[v] && v!=HH) mn = min(mn, (mindis[v]+w)/2.0);
            }
        }
        if(mn<mindis[u]) tmp.push_back({u, mn});
    }
    for(auto [u, dis]:tmp) {
        mindis[u] = min(mindis[u], dis);
    }
}

double solve(int NN, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    HH = H; N = NN;
    K = min(K, 70);
    for(int i=0;i<N;i++) {
        adj[i].clear();
        reach[i] = 0;
        mindis[i] = 1e18;
    }
    for(int i=0;i<M;i++) {
        adj[x[i]].push_back({y[i], (double)c[i]});
        adj[y[i]].push_back({x[i], (double)c[i]});
    }
    dfs(0);
    if(!reach[H]) return -1;
    mindis[0] = 0;
    for(int i=1;i<N;i++) {
        if(reach[i] && arr[i]==0) {
            mindis[i] = 0;
        }
    }
    for(int i=0;i<=K;i++) dij(arr);
    return mindis[H];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3416 KB Correct.
2 Correct 33 ms 3420 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3668 KB Correct.
2 Correct 130 ms 3668 KB Correct.
3 Correct 127 ms 3684 KB Correct.
4 Correct 140 ms 3668 KB Correct.
5 Correct 133 ms 3664 KB Correct.
6 Correct 185 ms 4896 KB Correct.
7 Correct 247 ms 4856 KB Correct.
8 Correct 110 ms 6108 KB Correct.
9 Correct 67 ms 3536 KB Correct.
10 Correct 67 ms 3536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3800 KB Correct.
2 Correct 135 ms 3632 KB Correct.
3 Correct 111 ms 3624 KB Correct.
4 Correct 73 ms 3548 KB Correct.
5 Correct 75 ms 3532 KB Correct.
6 Correct 37 ms 4464 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9136 KB Correct.
2 Correct 97 ms 3624 KB Correct.
3 Correct 80 ms 3668 KB Correct.
4 Correct 81 ms 3636 KB Correct.
5 Correct 57 ms 3540 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3672 KB Correct.
2 Correct 52 ms 3712 KB Correct.
3 Correct 57 ms 3760 KB Correct.
4 Correct 106 ms 4996 KB Correct.
5 Correct 35 ms 3416 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3796 KB Correct.
2 Correct 45 ms 3792 KB Correct.
3 Correct 34 ms 10068 KB Correct.
4 Correct 57 ms 4828 KB Correct.
5 Correct 39 ms 3752 KB Correct.
6 Correct 50 ms 3676 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3672 KB Correct.
2 Correct 16 ms 3676 KB Correct.
3 Correct 563 ms 15568 KB Correct.
4 Correct 397 ms 6768 KB Correct.
5 Correct 264 ms 12212 KB Correct.
6 Correct 105 ms 10180 KB Correct.
7 Correct 372 ms 6616 KB Correct.
8 Correct 283 ms 3992 KB Correct.
9 Correct 62 ms 3812 KB Correct.
10 Correct 53 ms 3932 KB Correct.
11 Correct 235 ms 3924 KB Correct.
12 Correct 68 ms 3672 KB Correct.
13 Correct 64 ms 3792 KB Correct.
14 Correct 307 ms 9804 KB Correct.
15 Correct 316 ms 5452 KB Correct.
16 Correct 58 ms 3672 KB Correct.
17 Correct 79 ms 3676 KB Correct.
18 Correct 66 ms 3804 KB Correct.
19 Correct 232 ms 3936 KB Correct.
20 Correct 5 ms 3416 KB Correct.
21 Correct 6 ms 3420 KB Correct.
22 Correct 10 ms 4188 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3788 KB Correct.
2 Correct 22 ms 3672 KB Correct.
3 Correct 1130 ms 18356 KB Correct.
4 Correct 413 ms 4616 KB Correct.
5 Correct 574 ms 12676 KB Correct.
6 Correct 196 ms 10056 KB Correct.
7 Correct 535 ms 9248 KB Correct.
8 Correct 333 ms 3920 KB Correct.
9 Correct 108 ms 3924 KB Correct.
10 Correct 96 ms 3924 KB Correct.
11 Correct 220 ms 3668 KB Correct.
12 Correct 118 ms 3696 KB Correct.
13 Correct 112 ms 3676 KB Correct.
14 Correct 1010 ms 10964 KB Correct.
15 Correct 1262 ms 10164 KB Correct.
16 Correct 616 ms 6428 KB Correct.
17 Correct 390 ms 3924 KB Correct.
18 Correct 95 ms 3676 KB Correct.
19 Correct 151 ms 3820 KB Correct.
20 Correct 111 ms 3780 KB Correct.
21 Correct 462 ms 3924 KB Correct.
22 Correct 7 ms 3420 KB Correct.
23 Correct 8 ms 3608 KB Correct.
24 Correct 16 ms 4188 KB Correct.