oj.uz

Submission #751016

# Submission time Handle Problem Language Result Execution time Memory
751016 2023-05-30T19:29:21 Z Gurban Cyberland (APIO23_cyberland) C++17
100 / 100
 846 ms 11880 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) {
    K = min(K,66);
    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 31 ms 2780 KB Correct.
2 Correct 32 ms 2732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Correct.
2 Correct 26 ms 2808 KB Correct.
3 Correct 24 ms 2772 KB Correct.
4 Correct 25 ms 2772 KB Correct.
5 Correct 25 ms 2848 KB Correct.
6 Correct 23 ms 3668 KB Correct.
7 Correct 30 ms 3712 KB Correct.
8 Correct 15 ms 4600 KB Correct.
9 Correct 25 ms 2732 KB Correct.
10 Correct 26 ms 2732 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2828 KB Correct.
2 Correct 27 ms 2824 KB Correct.
3 Correct 28 ms 2840 KB Correct.
4 Correct 27 ms 2732 KB Correct.
5 Correct 28 ms 2740 KB Correct.
6 Correct 7 ms 3412 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 8572 KB Correct.
2 Correct 134 ms 2780 KB Correct.
3 Correct 124 ms 2804 KB Correct.
4 Correct 127 ms 2780 KB Correct.
5 Correct 93 ms 2720 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2856 KB Correct.
2 Correct 29 ms 2920 KB Correct.
3 Correct 21 ms 2900 KB Correct.
4 Correct 25 ms 4032 KB Correct.
5 Correct 21 ms 2748 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2936 KB Correct.
2 Correct 21 ms 2928 KB Correct.
3 Correct 50 ms 10004 KB Correct.
4 Correct 17 ms 3796 KB Correct.
5 Correct 27 ms 2644 KB Correct.
6 Correct 26 ms 2900 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2908 KB Correct.
2 Correct 24 ms 2968 KB Correct.
3 Correct 334 ms 11880 KB Correct.
4 Correct 223 ms 5164 KB Correct.
5 Correct 485 ms 10480 KB Correct.
6 Correct 188 ms 9288 KB Correct.
7 Correct 221 ms 5000 KB Correct.
8 Correct 175 ms 3092 KB Correct.
9 Correct 100 ms 2892 KB Correct.
10 Correct 92 ms 2952 KB Correct.
11 Correct 169 ms 3052 KB Correct.
12 Correct 117 ms 2904 KB Correct.
13 Correct 106 ms 2968 KB Correct.
14 Correct 220 ms 7320 KB Correct.
15 Correct 200 ms 4020 KB Correct.
16 Correct 103 ms 2896 KB Correct.
17 Correct 118 ms 2892 KB Correct.
18 Correct 102 ms 2940 KB Correct.
19 Correct 314 ms 2848 KB Correct.
20 Correct 7 ms 2644 KB Correct.
21 Correct 9 ms 2764 KB Correct.
22 Correct 16 ms 3404 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 2924 KB Correct.
2 Correct 45 ms 2960 KB Correct.
3 Correct 204 ms 11596 KB Correct.
4 Correct 236 ms 3608 KB Correct.
5 Correct 846 ms 10420 KB Correct.
6 Correct 336 ms 9188 KB Correct.
7 Correct 339 ms 6868 KB Correct.
8 Correct 212 ms 3004 KB Correct.
9 Correct 196 ms 2964 KB Correct.
10 Correct 180 ms 2984 KB Correct.
11 Correct 161 ms 2892 KB Correct.
12 Correct 243 ms 2892 KB Correct.
13 Correct 211 ms 2856 KB Correct.
14 Correct 729 ms 8296 KB Correct.
15 Correct 631 ms 7584 KB Correct.
16 Correct 349 ms 4960 KB Correct.
17 Correct 233 ms 3200 KB Correct.
18 Correct 205 ms 2924 KB Correct.
19 Correct 272 ms 2864 KB Correct.
20 Correct 206 ms 2952 KB Correct.
21 Correct 657 ms 2944 KB Correct.
22 Correct 11 ms 2644 KB Correct.
23 Correct 19 ms 2772 KB Correct.
24 Correct 26 ms 3292 KB Correct.