oj.uz

Submission #978230

# Submission time Handle Problem Language Result Execution time Memory
978230 2024-05-09T04:12:27 Z Tsagana Cyberland (APIO23_cyberland) C++17
100 / 100
 1361 ms 20900 KB 
#include "cyberland.h"

// START 
#include <bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define pi pair<int, int >
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define pid pair<int, double>
#define pdi pair<double, int>
 
using namespace std;
 
vector<pid> adj[100005];
double mindis[100005];
bool reach[100005];
int h, n;
 
void dfs(int u) {
    reach[u] = 1;
    if (u == h) return;
    for (auto [v, w]: adj[u]) {
        if (!reach[v]) dfs(v);
    }
}
 
void dij(vector<int> &arr) {
    priority_queue<pdi, vector<pdi>, greater<pdi>> 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().S;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (u == h) 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 != h) mn = min(mn, (mindis[v] + w) / 2.0);
            }
        }
        if(mn < mindis[u]) tmp.pb({u, mn});
    }
    for (auto [u, dis]: tmp) {
        mindis[u] = min(mindis[u], dis);
    }
}
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    h = H; n = N;
    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]].pb({y[i], (double)c[i]});
        adj[y[i]].pb({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];
}
//END

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3176 KB Correct.
2 Correct 42 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3756 KB Correct.
2 Correct 139 ms 3924 KB Correct.
3 Correct 129 ms 3820 KB Correct.
4 Correct 144 ms 4008 KB Correct.
5 Correct 137 ms 3828 KB Correct.
6 Correct 186 ms 5080 KB Correct.
7 Correct 246 ms 4972 KB Correct.
8 Correct 110 ms 5884 KB Correct.
9 Correct 72 ms 3732 KB Correct.
10 Correct 69 ms 3664 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3920 KB Correct.
2 Correct 130 ms 3836 KB Correct.
3 Correct 125 ms 3908 KB Correct.
4 Correct 76 ms 3760 KB Correct.
5 Correct 75 ms 3724 KB Correct.
6 Correct 38 ms 4232 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 10548 KB Correct.
2 Correct 89 ms 3988 KB Correct.
3 Correct 85 ms 3748 KB Correct.
4 Correct 82 ms 3924 KB Correct.
5 Correct 57 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3924 KB Correct.
2 Correct 56 ms 4068 KB Correct.
3 Correct 77 ms 4080 KB Correct.
4 Correct 114 ms 5532 KB Correct.
5 Correct 36 ms 3496 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4000 KB Correct.
2 Correct 43 ms 3988 KB Correct.
3 Correct 40 ms 11700 KB Correct.
4 Correct 60 ms 4708 KB Correct.
5 Correct 49 ms 3600 KB Correct.
6 Correct 57 ms 4024 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3972 KB Correct.
2 Correct 13 ms 3160 KB Correct.
3 Correct 734 ms 17796 KB Correct.
4 Correct 413 ms 8288 KB Correct.
5 Correct 296 ms 13456 KB Correct.
6 Correct 111 ms 10836 KB Correct.
7 Correct 418 ms 7464 KB Correct.
8 Correct 296 ms 5188 KB Correct.
9 Correct 66 ms 3872 KB Correct.
10 Correct 57 ms 4008 KB Correct.
11 Correct 241 ms 5096 KB Correct.
12 Correct 69 ms 3924 KB Correct.
13 Correct 68 ms 4108 KB Correct.
14 Correct 307 ms 10856 KB Correct.
15 Correct 322 ms 6660 KB Correct.
16 Correct 60 ms 3908 KB Correct.
17 Correct 81 ms 4164 KB Correct.
18 Correct 76 ms 3968 KB Correct.
19 Correct 239 ms 4788 KB Correct.
20 Correct 5 ms 2904 KB Correct.
21 Correct 7 ms 2908 KB Correct.
22 Correct 10 ms 3676 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3956 KB Correct.
2 Correct 23 ms 3164 KB Correct.
3 Correct 1240 ms 20900 KB Correct.
4 Correct 405 ms 6068 KB Correct.
5 Correct 562 ms 13444 KB Correct.
6 Correct 209 ms 11224 KB Correct.
7 Correct 585 ms 10924 KB Correct.
8 Correct 327 ms 5180 KB Correct.
9 Correct 102 ms 3920 KB Correct.
10 Correct 93 ms 3804 KB Correct.
11 Correct 214 ms 4008 KB Correct.
12 Correct 119 ms 4112 KB Correct.
13 Correct 119 ms 3988 KB Correct.
14 Correct 1058 ms 12068 KB Correct.
15 Correct 1361 ms 11516 KB Correct.
16 Correct 636 ms 7408 KB Correct.
17 Correct 396 ms 5236 KB Correct.
18 Correct 99 ms 4060 KB Correct.
19 Correct 142 ms 4176 KB Correct.
20 Correct 119 ms 4076 KB Correct.
21 Correct 458 ms 4920 KB Correct.
22 Correct 7 ms 2908 KB Correct.
23 Correct 10 ms 2908 KB Correct.
24 Correct 17 ms 3676 KB Correct.