oj.uz

답안 #751015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751015 2023-05-30T19:28:25 Z Gurban 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 440 ms 11748 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,50);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2756 KB Correct.
2 Correct 30 ms 2756 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2764 KB Correct.
2 Correct 25 ms 2772 KB Correct.
3 Correct 23 ms 2860 KB Correct.
4 Correct 25 ms 2772 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 22 ms 3720 KB Correct.
7 Correct 28 ms 3668 KB Correct.
8 Correct 14 ms 4560 KB Correct.
9 Correct 25 ms 2644 KB Correct.
10 Correct 25 ms 2740 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2820 KB Correct.
2 Correct 28 ms 2772 KB Correct.
3 Correct 27 ms 2824 KB Correct.
4 Correct 28 ms 2644 KB Correct.
5 Correct 27 ms 2772 KB Correct.
6 Correct 8 ms 3424 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 8560 KB Correct.
2 Correct 137 ms 2900 KB Correct.
3 Correct 120 ms 2780 KB Correct.
4 Correct 132 ms 2896 KB Correct.
5 Correct 102 ms 2704 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2852 KB Correct.
2 Correct 24 ms 2944 KB Correct.
3 Correct 23 ms 2928 KB Correct.
4 Correct 23 ms 3988 KB Correct.
5 Correct 22 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2860 KB Correct.
2 Correct 22 ms 2932 KB Correct.
3 Correct 47 ms 10048 KB Correct.
4 Correct 17 ms 3768 KB Correct.
5 Correct 24 ms 2644 KB Correct.
6 Correct 23 ms 2968 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 2892 KB Correct.
2 Correct 22 ms 2920 KB Correct.
3 Correct 348 ms 11748 KB Correct.
4 Correct 214 ms 5088 KB Correct.
5 Correct 440 ms 10432 KB Correct.
6 Correct 181 ms 9084 KB Correct.
7 Correct 219 ms 5048 KB Correct.
8 Correct 168 ms 3232 KB Correct.
9 Correct 96 ms 2956 KB Correct.
10 Correct 90 ms 3004 KB Correct.
11 Correct 150 ms 3044 KB Correct.
12 Correct 113 ms 2956 KB Correct.
13 Correct 105 ms 2964 KB Correct.
14 Correct 212 ms 7376 KB Correct.
15 Correct 200 ms 4148 KB Correct.
16 Correct 103 ms 2968 KB Correct.
17 Correct 123 ms 3072 KB Correct.
18 Correct 101 ms 2904 KB Correct.
19 Correct 312 ms 2772 KB Correct.
20 Correct 7 ms 2644 KB Correct.
21 Correct 9 ms 2764 KB Correct.
22 Correct 16 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 3032 KB Correct.
2 Correct 35 ms 2960 KB Correct.
3 Incorrect 165 ms 11600 KB Wrong Answer.
4 Halted 0 ms 0 KB -