oj.uz

Submission #968394

# Submission time Handle Problem Language Result Execution time Memory
968394 2024-04-23T11:28:10 Z akacool445k Cyberland (APIO23_cyberland) C++17
68 / 100
 1102 ms 193448 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
 
// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < double , int >
#define vint vector < int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)

const double inf = 1e18 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
 
vector < vector < pint > > adj(mxn);
vint arr_;
double dis[77][mxn];
bool vis[mxn];

priority_queue < pint > q[77];

void dfs(int x , int par , int H) {
    if (vis[x]) return;
    vis[x] = 1;
    if (x == H) return;
    if (arr_[x] == 0) q[0].push({0 , x});
    for (pint i : adj[x]) {
        if (i.ss == par) continue;
        dfs(i.ss , x , H);
    }
}
 
double solve(int n , int m , int k , int H , vint x , vint y , vint c , vint arr) {

    for (int i = 0; i < n; i++) {
        adj[i].clear();
        vis[i] = 0;
    }

    k = min(k , 75);

    for (int i = 0; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = -1;
        }
    }

    arr_ = arr;
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back({c[i] , y[i]});
        adj[y[i]].push_back({c[i] , x[i]});
    }

    dfs(0 , 0 , H);
    q[0].push({0 , 0});

    for (int i = 0; i <= k; i++) {
        for(int u = 0; u < n; u++)
            vis[u] = 0;
        while (!q[i].empty()) {
            pint p = q[i].top();
            q[i].pop();
            
            if (vis[p.ss]) continue;
            vis[p.ss] = 1;
            dis[i][p.ss] = -p.ff;
            if (p.ss == H) continue;

            for (pint j : adj[p.ss]) {
                if (j.ss == 0) continue;
                if (arr[j.ss] == 0) continue;
                if (!vis[j.ss]) q[i].push({p.ff - j.ff , j.ss});
                if (arr[j.ss] == 2) q[i+1].push({(p.ff - j.ff) / 2.0 , j.ss});
            }
        }
    }

    double ans = inf;
    for (int i = 0; i <= k; i++) {
        if (dis[i][H] != -1) ans = min(ans , dis[i][H]);
    }

    if (ans == inf) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 52492 KB Correct.
2 Correct 25 ms 52452 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 52572 KB Correct.
2 Correct 27 ms 52316 KB Correct.
3 Correct 27 ms 52316 KB Correct.
4 Correct 32 ms 52316 KB Correct.
5 Correct 27 ms 52572 KB Correct.
6 Correct 24 ms 53340 KB Correct.
7 Correct 31 ms 53332 KB Correct.
8 Correct 18 ms 54104 KB Correct.
9 Correct 26 ms 52316 KB Correct.
10 Correct 25 ms 52316 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 52316 KB Correct.
2 Correct 34 ms 52552 KB Correct.
3 Correct 37 ms 52572 KB Correct.
4 Correct 28 ms 52316 KB Correct.
5 Correct 28 ms 52312 KB Correct.
6 Correct 11 ms 53080 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 63476 KB Correct.
2 Correct 74 ms 53068 KB Correct.
3 Correct 67 ms 53076 KB Correct.
4 Correct 83 ms 52952 KB Correct.
5 Correct 45 ms 52704 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 52824 KB Correct.
2 Correct 28 ms 52572 KB Correct.
3 Correct 28 ms 52572 KB Correct.
4 Correct 30 ms 54176 KB Correct.
5 Correct 25 ms 52416 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 52528 KB Correct.
2 Correct 26 ms 52920 KB Correct.
3 Correct 55 ms 61168 KB Correct.
4 Correct 21 ms 53596 KB Correct.
5 Correct 36 ms 52316 KB Correct.
6 Correct 27 ms 52684 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 53940 KB Correct.
2 Correct 33 ms 53344 KB Correct.
3 Correct 402 ms 44300 KB Correct.
4 Correct 220 ms 47048 KB Correct.
5 Correct 463 ms 85592 KB Correct.
6 Correct 376 ms 85240 KB Correct.
7 Correct 221 ms 53104 KB Correct.
8 Incorrect 162 ms 52816 KB Wrong Answer.
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 126212 KB Correct.
2 Correct 62 ms 125980 KB Correct.
3 Correct 199 ms 140092 KB Correct.
4 Correct 259 ms 125712 KB Correct.
5 Correct 1102 ms 186120 KB Correct.
6 Correct 879 ms 193448 KB Correct.
7 Correct 521 ms 133920 KB Correct.
8 Incorrect 194 ms 124752 KB Wrong Answer.
9 Halted 0 ms 0 KB -