oj.uz

Submission #982195

# Submission time Handle Problem Language Result Execution time Memory
982195 2024-05-14T02:38:03 Z sopaconk Cyberland (APIO23_cyberland) C++17
68 / 100
 46 ms 11092 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using lli=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,lli>>> 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<bool>> nodes (K+1, vector<bool> (N, false));
    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]=pow2[i-1]/2;
    }  
    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(!reachable[c]) continue;
        if(!firsti && c==H) continue;
        firsti=false;
        if(nodes[b][c]) continue;
        nodes[b][c]=1;
        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];
         //   deb(cam);
            if(arr[adj[c][i].first]==2){
                if(b+1>=K+1) continue;
                if(!nodes[b+1][adj[c][i].first])
                pq.push({a+cam, {b+1, adj[c][i].first}});
            }
            if(!nodes[b][adj[c][i].first])
                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, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=0; i<adj[c].size(); ++i){
      |                      ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 348 KB Correct.
2 Correct 32 ms 892 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 604 KB Correct.
2 Correct 20 ms 604 KB Correct.
3 Correct 19 ms 604 KB Correct.
4 Correct 19 ms 600 KB Correct.
5 Correct 20 ms 600 KB Correct.
6 Correct 15 ms 1440 KB Correct.
7 Correct 20 ms 1440 KB Correct.
8 Correct 8 ms 2396 KB Correct.
9 Correct 23 ms 344 KB Correct.
10 Correct 24 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 344 KB Correct.
2 Correct 21 ms 348 KB Correct.
3 Correct 20 ms 604 KB Correct.
4 Correct 24 ms 348 KB Correct.
5 Correct 22 ms 348 KB Correct.
6 Correct 4 ms 1116 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6492 KB Correct.
2 Correct 18 ms 600 KB Correct.
3 Correct 17 ms 604 KB Correct.
4 Correct 17 ms 596 KB Correct.
5 Correct 23 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB Correct.
2 Correct 23 ms 604 KB Correct.
3 Correct 21 ms 604 KB Correct.
4 Correct 20 ms 1372 KB Correct.
5 Correct 20 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 604 KB Correct.
2 Correct 17 ms 604 KB Correct.
3 Correct 33 ms 8528 KB Correct.
4 Correct 11 ms 1208 KB Correct.
5 Correct 21 ms 348 KB Correct.
6 Correct 18 ms 604 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Correct.
2 Correct 3 ms 604 KB Correct.
3 Incorrect 41 ms 10576 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Correct.
2 Correct 3 ms 600 KB Correct.
3 Incorrect 46 ms 11092 KB Wrong Answer.
4 Halted 0 ms 0 KB -