Submission #982204

#	Time	Username	Problem	Language	Result	Execution time	Memory
982204		sopaconk	Cyberland (APIO23_cyberland)	C++17	44 / 100	2223 ms	164744 KiB

cyberland

#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,0}});
    for(lli i=0; i<N; ++i){
        if(arr[i]==0){
            pq.push({0,{0,i}});
        }
    }

    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(nodes[b][c]) continue;
        nodes[b][c]=true;
       if(c==H) 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(arr[adj[c][i].first]==0){
                if(!nodes[b][adj[c][i].first]){
                    pq.push({0, {b, adj[c][i].first}});
                }
            }
            if(!nodes[b][adj[c][i].first])
                pq.push({a+cam, {b, adj[c][i].first}});
        }

    }




    
    return -1;
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:56: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]
   56 |         for(int i=0; i<adj[c].size(); ++i){
      |                      ~^~~~~~~~~~~~~~
cyberland.cpp:46:10: warning: unused variable 'firsti' [-Wunused-variable]
   46 |     bool firsti=true;
      |          ^~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3