oj.uz

답안 #986701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986701 2024-05-21T04:22:20 Z CSQ31 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 560 ms 108320 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
ld dist[61][111111];
ld pw[61];
struct node{
    int v,k;
    ld dist = 0;
    node(int _v,int _k,ld _dist = 0){
        v = _v;
        k = _k;
        dist = _dist;
    }
};
 
struct comp
{
    bool operator() (node const &a, node const &b) { return a.dist - b.dist > 1e-10; }
};
vector<pair<int,int>>adj[111111];
double solve(int n, int m,int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    priority_queue<node,vector<node>,comp>pq;
    for(int j=0;j<n;j++){
        adj[j].clear();
        for(int i=0;i<=60;i++){
            dist[i][j] = 1e15;
        }
    }
    pw[0] = 1;
    for(int i=1;i<=60;i++)pw[i] = pw[i-1]*2;
    for(int i=0;i<m;i++){
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    K = min(K,60);
    dist[0][H] = 0;
    pq.push(node(H,0));
    while(!pq.empty()){
        node tmp = pq.top();
        int v = tmp.v;
        int k = tmp.k;
        //cout<<v<<" "<<k<<" "<<tmp.dist<<" "<<dist[k][v]<<'\n';
        pq.pop();
        if(abs(tmp.dist - dist[k][v]) > 1e-10)continue;
        if(arr[v] == 0)continue;
 
        for(pair<int,int>x : adj[v]){
            int u = x.first;
          if(u == H)continue;
            ld w = x.second/pw[k];
            if(dist[k][u] - dist[k][v] - w > 1e-10){
                dist[k][u] = dist[k][v] + w;
                pq.push(node(u,k,dist[k][u]));
            }
            if(arr[u] == 2 && k+1 <= K){
                if(dist[k+1][u] - dist[k][v] - w > 1e-10){
                    dist[k+1][u] = dist[k][v] + w;
                    pq.push(node(u,k+1,dist[k+1][u]));
                }
 
            }
        }
    }
    ld ans = 1e18;
    for(int i=0;i<=K;i++)ans = min(ans,dist[i][0]);
    queue<int>q;
    vector<int>vis(n,0);
    q.push(0);
    vis[0] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(arr[v] == 0){
            for(int i=0;i<=K;i++)ans = min(ans,dist[i][v]);   
        }
      if(v==H)continue;
        for(pair<int,int>x:adj[v]){
            int u = x.first;
            if(!vis[u]){
                q.push(u);
                vis[u] = 1;
            }
        }
    }
    if(!vis[H])return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 7512 KB Correct.
2 Correct 26 ms 7508 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 9200 KB Correct.
2 Correct 37 ms 5456 KB Correct.
3 Correct 39 ms 5460 KB Correct.
4 Correct 36 ms 5580 KB Correct.
5 Correct 36 ms 5720 KB Correct.
6 Correct 34 ms 14472 KB Correct.
7 Correct 44 ms 19540 KB Correct.
8 Correct 24 ms 26968 KB Correct.
9 Correct 34 ms 8028 KB Correct.
10 Correct 34 ms 8028 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 9048 KB Correct.
2 Correct 34 ms 9056 KB Correct.
3 Correct 35 ms 8408 KB Correct.
4 Correct 40 ms 8452 KB Correct.
5 Correct 36 ms 8028 KB Correct.
6 Correct 13 ms 15196 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 65872 KB Correct.
2 Correct 33 ms 9052 KB Correct.
3 Correct 30 ms 11092 KB Correct.
4 Correct 34 ms 9304 KB Correct.
5 Correct 43 ms 8020 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 9048 KB Correct.
2 Correct 34 ms 9296 KB Correct.
3 Correct 33 ms 9288 KB Correct.
4 Correct 35 ms 17852 KB Correct.
5 Correct 31 ms 8024 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 9064 KB Correct.
2 Correct 29 ms 8984 KB Correct.
3 Correct 78 ms 83796 KB Correct.
4 Correct 27 ms 14680 KB Correct.
5 Correct 33 ms 8028 KB Correct.
6 Correct 32 ms 9016 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 9428 KB Correct.
2 Correct 22 ms 9068 KB Correct.
3 Correct 472 ms 103820 KB Correct.
4 Correct 286 ms 30716 KB Correct.
5 Correct 394 ms 46644 KB Correct.
6 Correct 217 ms 22996 KB Correct.
7 Correct 354 ms 32580 KB Correct.
8 Correct 207 ms 12624 KB Correct.
9 Correct 104 ms 9392 KB Correct.
10 Correct 96 ms 9372 KB Correct.
11 Correct 186 ms 10356 KB Correct.
12 Correct 103 ms 9552 KB Correct.
13 Correct 106 ms 9320 KB Correct.
14 Correct 306 ms 54608 KB Correct.
15 Correct 308 ms 21368 KB Correct.
16 Correct 110 ms 9404 KB Correct.
17 Correct 113 ms 9628 KB Correct.
18 Correct 101 ms 9384 KB Correct.
19 Correct 167 ms 6480 KB Correct.
20 Correct 11 ms 7260 KB Correct.
21 Correct 12 ms 8028 KB Correct.
22 Correct 20 ms 8796 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 9656 KB Correct.
2 Correct 38 ms 9052 KB Correct.
3 Incorrect 560 ms 108320 KB Wrong Answer.
4 Halted 0 ms 0 KB -