oj.uz

Submission #1081549

# Submission time Handle Problem Language Result Execution time Memory
1081549 2024-08-30T07:15:09 Z KasymK Cyberland (APIO23_cyberland) C++17
100 / 100
 1468 ms 64452 KB 
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second   
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a){
    umin(k, 69);
    vector<pii> adj[n];
    for(int i = 0; i < m; ++i){
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    vector<bool> vis(n, 0);
    queue<int> Q;
    Q.push(0);
    vis[0] = 1;
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        if(x == h)
            continue;
        for(auto &[i, w] : adj[x])
            if(!vis[i]){
                vis[i] = 1;
                Q.push(i);
            }
    }
    if(!vis[h])
        return -1;
    using node = pair<double, int>;
    priority_queue<node, vector<node>, greater<node>> q[k+2];
    vector<vector<bool>> mrk(n, vector<bool> (k+1, 0));
    q[0].push({0, 0});
    for(int i = 1; i < n; ++i)
        if(!a[i] and vis[i])
            q[0].push({0, i});
    int pk = 0;
    double answer = 1e18;
    while(pk <= k){
        if(q[pk].empty()){
            ++pk;
            continue;
        }
        auto [val, x] = q[pk].top();
        q[pk].pop();
        if(x == h){
            umin(answer, val);
            mrk[x][pk] = 1;
        }
        if(mrk[x][pk]) 
            continue;
        mrk[x][pk] = 1;
        for(auto [i, w] : adj[x])
            if(a[i]){
                if(!mrk[i][pk])
                    q[pk].push({val+w, i});
                if(a[i] == 2)
                    q[pk+1].push({(val+w)/2, i});
            }
    }
    return answer;
}

// int main(){
//     double kk = solve(3, 2, 30, 2,{1, 2},{2, 0},{12, 4},{1, 2, 1});
//     double kk1 = solve(4, 4, 30, 3,{0, 0, 1, 2},{1, 2, 3, 3},{5, 4, 2, 4},{1, 0, 2, 1});
//     if(kk == 4.0 and kk1 == 2.0)
//         puts("Correct.");
//     else
//         puts("Wrong Answer.");
//     return 0;
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Correct.
2 Correct 16 ms 848 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1224 KB Correct.
2 Correct 26 ms 1364 KB Correct.
3 Correct 25 ms 1400 KB Correct.
4 Correct 28 ms 1364 KB Correct.
5 Correct 27 ms 1372 KB Correct.
6 Correct 23 ms 2580 KB Correct.
7 Correct 31 ms 2500 KB Correct.
8 Correct 15 ms 3932 KB Correct.
9 Correct 24 ms 1116 KB Correct.
10 Correct 24 ms 1008 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1368 KB Correct.
2 Correct 27 ms 1160 KB Correct.
3 Correct 28 ms 1360 KB Correct.
4 Correct 27 ms 1104 KB Correct.
5 Correct 26 ms 1112 KB Correct.
6 Correct 7 ms 2140 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 13856 KB Correct.
2 Correct 73 ms 1624 KB Correct.
3 Correct 68 ms 1520 KB Correct.
4 Correct 69 ms 1516 KB Correct.
5 Correct 47 ms 1104 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1368 KB Correct.
2 Correct 24 ms 1372 KB Correct.
3 Correct 25 ms 1552 KB Correct.
4 Correct 25 ms 2176 KB Correct.
5 Correct 21 ms 972 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1368 KB Correct.
2 Correct 20 ms 1116 KB Correct.
3 Correct 32 ms 8532 KB Correct.
4 Correct 14 ms 2132 KB Correct.
5 Correct 28 ms 1108 KB Correct.
6 Correct 22 ms 1116 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1716 KB Correct.
2 Correct 21 ms 1372 KB Correct.
3 Correct 382 ms 18952 KB Correct.
4 Correct 231 ms 5428 KB Correct.
5 Correct 498 ms 32064 KB Correct.
6 Correct 407 ms 32488 KB Correct.
7 Correct 241 ms 5572 KB Correct.
8 Correct 160 ms 2264 KB Correct.
9 Correct 92 ms 1728 KB Correct.
10 Correct 83 ms 1916 KB Correct.
11 Correct 145 ms 2116 KB Correct.
12 Correct 94 ms 1756 KB Correct.
13 Correct 99 ms 1704 KB Correct.
14 Correct 252 ms 9612 KB Correct.
15 Correct 212 ms 3752 KB Correct.
16 Correct 93 ms 1784 KB Correct.
17 Correct 102 ms 1732 KB Correct.
18 Correct 101 ms 1684 KB Correct.
19 Correct 208 ms 2172 KB Correct.
20 Correct 5 ms 600 KB Correct.
21 Correct 6 ms 860 KB Correct.
22 Correct 38 ms 4188 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 2148 KB Correct.
2 Correct 40 ms 2136 KB Correct.
3 Correct 213 ms 18000 KB Correct.
4 Correct 245 ms 3884 KB Correct.
5 Correct 1091 ms 59720 KB Correct.
6 Correct 916 ms 64452 KB Correct.
7 Correct 528 ms 8832 KB Correct.
8 Correct 172 ms 2776 KB Correct.
9 Correct 147 ms 2452 KB Correct.
10 Correct 150 ms 2520 KB Correct.
11 Correct 157 ms 1616 KB Correct.
12 Correct 159 ms 2560 KB Correct.
13 Correct 168 ms 2564 KB Correct.
14 Correct 1468 ms 30044 KB Correct.
15 Correct 788 ms 12644 KB Correct.
16 Correct 400 ms 6200 KB Correct.
17 Correct 209 ms 2956 KB Correct.
18 Correct 155 ms 2532 KB Correct.
19 Correct 178 ms 2620 KB Correct.
20 Correct 159 ms 2728 KB Correct.
21 Correct 344 ms 3408 KB Correct.
22 Correct 8 ms 604 KB Correct.
23 Correct 10 ms 1100 KB Correct.
24 Correct 78 ms 8104 KB Correct.