oj.uz

Submission #756935

# Submission time Handle Problem Language Result Execution time Memory
756935 2023-06-12T11:27:57 Z doowey Cyberland (APIO23_cyberland) C++17
100 / 100
 1522 ms 92744 KB 
#include <bits/stdc++.h>
#include "cyberland.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;
const int K = 100;
vector<pii> T[N];


bool can[N];
bool vv[N];
int A[N];
int ban;

void dfs(int u){
    vv[u]=true;
    if(u == 0 || A[u] == 0) can[u] = true;
    for(auto x : T[u]){
        if(!vv[x.fi] && x.fi != ban){
            dfs(x.fi);
        }
    }
}

double d[K][N];
double bins[K];
bool vis[K][N];

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, 90);
    bins[0] = 1.0;
    for(int i = 1; i <= k ; i ++ ){
        bins[i]=bins[i-1]*0.5;
    }
    ban = h;
    for(int i = 0 ; i < n; i ++ ){
        T[i].clear();
        can[i] = vv[i] = false;
        A[i] = arr[i];
    }
    for(int i = 0 ; i < m ; i ++ ){
        T[x[i]].push_back(mp(y[i], c[i]));
        T[y[i]].push_back(mp(x[i], c[i]));
    }
    dfs(0);
    double dis;
    double nw;
    double op = 1e18;
    bool fix = false;
    for(int j = 0 ; j <= k ; j ++ ){
        for(int i = 0 ; i < n; i ++ ){
            d[j][i] = 1e18;
            vis[j][i] = false;
        }
        priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
        if(j == 0){
            d[j][h] = 0.0;
            pq.push(mp(0.0, h));
        }
        else{
            for(int i = 0 ; i < n; i ++ ){
                if(vis[j - 1][i] && A[i] == 2){
                    for(auto x : T[i]){
                        if(x.fi == h) continue;
                        nw = x.se * bins[j];
                        if(d[j][x.fi] > d[j - 1][i] + nw){
                            d[j][x.fi] = d[j - 1][i] + nw;
                            pq.push(mp(d[j][x.fi], x.fi));
                        }
                    }
                }
            }
        }
        while(!pq.empty()){
            int node = pq.top().se;
            dis = pq.top().fi;
            pq.pop();
            if(vis[j][node]) continue;
            vis[j][node] = true;
            if(can[node]){
                op = min(op, dis);
                fix = true;
            }
            for(auto x : T[node]){
                if(x.fi == h) continue;
                nw = x.se * bins[j];
                if(dis + nw < d[j][x.fi]){
                    d[j][x.fi] = dis + nw;
                    pq.push(mp(d[j][x.fi], x.fi));
                }
            }
        }
    }
    if(fix)
        return op;
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3136 KB Correct.
2 Correct 26 ms 3112 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 31 ms 3412 KB Correct.
3 Correct 27 ms 3412 KB Correct.
4 Correct 28 ms 3412 KB Correct.
5 Correct 28 ms 3400 KB Correct.
6 Correct 26 ms 6356 KB Correct.
7 Correct 34 ms 6276 KB Correct.
8 Correct 20 ms 9880 KB Correct.
9 Correct 29 ms 3076 KB Correct.
10 Correct 27 ms 3076 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3384 KB Correct.
2 Correct 28 ms 3384 KB Correct.
3 Correct 27 ms 3404 KB Correct.
4 Correct 30 ms 3080 KB Correct.
5 Correct 34 ms 3028 KB Correct.
6 Correct 8 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 24824 KB Correct.
2 Correct 198 ms 3392 KB Correct.
3 Correct 176 ms 3384 KB Correct.
4 Correct 185 ms 3376 KB Correct.
5 Correct 136 ms 3060 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 29 ms 3388 KB Correct.
3 Correct 26 ms 3472 KB Correct.
4 Correct 28 ms 6552 KB Correct.
5 Correct 27 ms 3028 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3540 KB Correct.
2 Correct 24 ms 3412 KB Correct.
3 Correct 61 ms 29080 KB Correct.
4 Correct 20 ms 5716 KB Correct.
5 Correct 28 ms 3072 KB Correct.
6 Correct 25 ms 3428 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 3444 KB Correct.
2 Correct 32 ms 3664 KB Correct.
3 Correct 403 ms 25264 KB Correct.
4 Correct 238 ms 9056 KB Correct.
5 Correct 782 ms 20072 KB Correct.
6 Correct 304 ms 11736 KB Correct.
7 Correct 243 ms 9312 KB Correct.
8 Correct 187 ms 4188 KB Correct.
9 Correct 136 ms 3484 KB Correct.
10 Correct 131 ms 3564 KB Correct.
11 Correct 170 ms 3568 KB Correct.
12 Correct 162 ms 3404 KB Correct.
13 Correct 150 ms 3412 KB Correct.
14 Correct 221 ms 11700 KB Correct.
15 Correct 215 ms 5812 KB Correct.
16 Correct 141 ms 3404 KB Correct.
17 Correct 167 ms 3568 KB Correct.
18 Correct 151 ms 3416 KB Correct.
19 Correct 430 ms 3380 KB Correct.
20 Correct 9 ms 3028 KB Correct.
21 Correct 14 ms 3284 KB Correct.
22 Correct 22 ms 3792 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 4592 KB Correct.
2 Correct 73 ms 5068 KB Correct.
3 Correct 317 ms 92744 KB Correct.
4 Correct 287 ms 7656 KB Correct.
5 Correct 1522 ms 38340 KB Correct.
6 Correct 621 ms 16968 KB Correct.
7 Correct 441 ms 22092 KB Correct.
8 Correct 283 ms 4880 KB Correct.
9 Correct 302 ms 4588 KB Correct.
10 Correct 288 ms 4556 KB Correct.
11 Correct 222 ms 3768 KB Correct.
12 Correct 379 ms 4572 KB Correct.
13 Correct 324 ms 4608 KB Correct.
14 Correct 1025 ms 38776 KB Correct.
15 Correct 927 ms 46672 KB Correct.
16 Correct 387 ms 15948 KB Correct.
17 Correct 305 ms 6792 KB Correct.
18 Correct 309 ms 4616 KB Correct.
19 Correct 374 ms 4720 KB Correct.
20 Correct 325 ms 4720 KB Correct.
21 Correct 1038 ms 4528 KB Correct.
22 Correct 18 ms 3668 KB Correct.
23 Correct 27 ms 4436 KB Correct.
24 Correct 42 ms 4800 KB Correct.