oj.uz

Submission #751014

# Submission time Handle Problem Language Result Execution time Memory
751014 2023-05-30T19:27:47 Z Gurban Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 11872 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const double inf = 1e16;
const int maxn=1e5+5;
const double eps = 0.00000001;
int D[maxn];
vector<pair<int,double>>E[maxn];

int p[maxn];

int ata(int x){
    if(p[x] == x) return x;
    return p[x] = ata(p[x]);
}

void un(int x,int y){
    int aa = ata(x);
    int bb = ata(y);
    p[bb] = aa;
}

bool con(int x,int y){
    int aa = ata(x);
    int bb = ata(y);
    return (aa == bb);
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    for(int i = 0;i < N;i++) E[i].clear(),p[i] = i;
    for(int i = 0;i < M;i++){
        E[x[i]].push_back({y[i],c[i]});
        E[y[i]].push_back({x[i],c[i]});
        if(x[i] != H and y[i] != H) un(x[i],y[i]);
    }
    vector<int>zeros = {0};
    vector<int>two;
    for(int i = 1;i < N;i++) if(arr[i] == 0 and con(0,i)) zeros.push_back(i);
    for(int i = 1;i < N;i++) if(arr[i] == 2) two.push_back(i);
    
    priority_queue<pair<double,int>>q;
    q.push({0,H});

    double ans = inf;
    double der = 1;

    for(int i = 0;i <= K;i++){
        vector<double>dis(N,inf);
        vector<bool>vis(N,0);
        while(!q.empty()){
            
            int x = q.top().second;
            double len = -q.top().first;
            q.pop();

            if(vis[x]) continue;
            vis[x] = 1;

            for(auto j : E[x]){
                if(j.first == H) continue;
                double now = (j.second / der) + len;
                if(dis[j.first] > now){
                    dis[j.first] = now;
                    q.push({-now,j.first}); 
                }
            }
        }
        for(auto j : zeros) ans = min(ans,dis[j]);
        for(auto j : two) if(abs(dis[j] - inf) >= eps) q.push({-dis[j],j});
        der *= 2;
    }
    if(abs(ans - inf) < eps) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2732 KB Correct.
2 Correct 30 ms 2812 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2772 KB Correct.
2 Correct 25 ms 2852 KB Correct.
3 Correct 24 ms 2816 KB Correct.
4 Correct 25 ms 2840 KB Correct.
5 Correct 25 ms 2824 KB Correct.
6 Correct 24 ms 3724 KB Correct.
7 Correct 29 ms 3668 KB Correct.
8 Correct 14 ms 4600 KB Correct.
9 Correct 24 ms 2724 KB Correct.
10 Correct 24 ms 2644 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2772 KB Correct.
2 Correct 29 ms 2852 KB Correct.
3 Correct 26 ms 2872 KB Correct.
4 Correct 28 ms 2644 KB Correct.
5 Correct 27 ms 2680 KB Correct.
6 Correct 7 ms 3412 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 8624 KB Correct.
2 Correct 136 ms 2772 KB Correct.
3 Correct 121 ms 2844 KB Correct.
4 Correct 128 ms 2896 KB Correct.
5 Correct 94 ms 2712 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3040 KB Correct.
2 Correct 24 ms 2900 KB Correct.
3 Correct 24 ms 2924 KB Correct.
4 Correct 24 ms 3964 KB Correct.
5 Correct 22 ms 2740 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2952 KB Correct.
2 Correct 21 ms 2972 KB Correct.
3 Correct 47 ms 10020 KB Correct.
4 Correct 17 ms 3780 KB Correct.
5 Correct 25 ms 2752 KB Correct.
6 Correct 24 ms 2920 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 2932 KB Correct.
2 Correct 24 ms 2940 KB Correct.
3 Correct 340 ms 11872 KB Correct.
4 Correct 223 ms 5088 KB Correct.
5 Correct 440 ms 10480 KB Correct.
6 Correct 200 ms 9160 KB Correct.
7 Correct 222 ms 5000 KB Correct.
8 Correct 170 ms 3148 KB Correct.
9 Correct 96 ms 2900 KB Correct.
10 Correct 92 ms 2880 KB Correct.
11 Correct 157 ms 3060 KB Correct.
12 Correct 114 ms 2948 KB Correct.
13 Correct 105 ms 2860 KB Correct.
14 Correct 212 ms 7440 KB Correct.
15 Correct 200 ms 4016 KB Correct.
16 Correct 103 ms 2896 KB Correct.
17 Correct 119 ms 2892 KB Correct.
18 Correct 104 ms 2908 KB Correct.
19 Correct 322 ms 2864 KB Correct.
20 Correct 7 ms 2644 KB Correct.
21 Correct 9 ms 2772 KB Correct.
22 Correct 18 ms 3392 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 2656 KB Time limit exceeded
2 Halted 0 ms 0 KB -