oj.uz

답안 #982180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982180 2024-05-14T02:21:47 Z sopaconk 사이버랜드 (APIO23_cyberland) C++17
68 / 100
 87 ms 87260 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using lli=long double;
#define deb(x) cout<<#x<<": "<<(x)<<endl;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int,int>>> adj (N);
    for(int i=0; i<M; ++i){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    vector<bool> reachable (N, false);
    vector<bool> visited (N, false);
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();q.pop();

        if(visited[x]) continue;
        reachable[x]=true;
        visited[x]=true;
        
        if(x==H) continue;
        for(auto y: adj[x]){
            if(visited[y.first]) continue;
            q.push(y.first);
        }
    }
    if(!reachable[H]) return -1;
    K=min(K, 48);
    vector<vector<lli>> nodes (K+1, vector<lli> (N, 1e17));
    priority_queue<pair<lli, pair<int,int>>, vector<pair<lli, pair<int,int>>>, greater<pair<lli, pair<int,int>>>> pq;
    pq.push({0, {0,H}});

    vector<lli> pow2 (K+1, 1);
    for(lli i=1; i<=K; ++i){
        pow2[i]=2*pow2[i-1];
    }  
    bool firsti=true;
    while(!pq.empty()){
        lli a=pq.top().first;
        int b=pq.top().second.first;
        int c=pq.top().second.second;
        pq.pop();
        if(!firsti && c==H) continue;
        firsti=false;
        if(nodes[b][c]<=a) continue;
   
        nodes[b][c]=a;
        if(c==0) return a;
        if(arr[c]==0 && reachable[c]) return a;
        for(int i=0; i<adj[c].size(); ++i){
            lli cam=adj[c][i].second/pow2[b];
            
            if(arr[adj[c][i].first]==2){
                if(b+1>=K+1) continue;
                if(nodes[b+1][adj[c][i].first]==1e17)
                pq.push({a+cam, {b+1, adj[c][i].first}});
            }
            if(nodes[b][adj[c][i].first]==1e17)
                pq.push({a+cam, {b, adj[c][i].first}});
        }

    }




    
    return -1;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=0; i<adj[c].size(); ++i){
      |                      ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 600 KB Correct.
2 Correct 21 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1092 KB Correct.
2 Correct 25 ms 1104 KB Correct.
3 Correct 24 ms 1000 KB Correct.
4 Correct 24 ms 1036 KB Correct.
5 Correct 24 ms 1204 KB Correct.
6 Correct 21 ms 6264 KB Correct.
7 Correct 28 ms 6048 KB Correct.
8 Correct 16 ms 12124 KB Correct.
9 Correct 22 ms 600 KB Correct.
10 Correct 22 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1044 KB Correct.
2 Correct 23 ms 1048 KB Correct.
3 Correct 21 ms 1108 KB Correct.
4 Correct 22 ms 604 KB Correct.
5 Correct 22 ms 604 KB Correct.
6 Correct 5 ms 5212 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 34456 KB Correct.
2 Correct 33 ms 1052 KB Correct.
3 Correct 34 ms 1076 KB Correct.
4 Correct 33 ms 1228 KB Correct.
5 Correct 44 ms 864 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1028 KB Correct.
2 Correct 25 ms 1024 KB Correct.
3 Correct 25 ms 1028 KB Correct.
4 Correct 24 ms 5920 KB Correct.
5 Correct 20 ms 600 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1140 KB Correct.
2 Correct 18 ms 960 KB Correct.
3 Correct 32 ms 7260 KB Correct.
4 Correct 19 ms 3796 KB Correct.
5 Correct 21 ms 604 KB Correct.
6 Correct 20 ms 1052 KB Correct.

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 936 KB Correct.
2 Correct 3 ms 884 KB Correct.
3 Incorrect 51 ms 37236 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1256 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Incorrect 87 ms 87260 KB Wrong Answer.
4 Halted 0 ms 0 KB -