Submission #1023239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023239		nam6	Cyberland (APIO23_cyberland)	C++17	92 / 100	3023 ms	38096 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std; 
 
const int MAXI_NOEUDS = 100*1000; 
const int MAXI_K = 70; 
vector<int> pouvoirs; 
int nbNoeuds, nbAretes, K, fin;
bool finAccess; 
 
struct Arc{
    int dest; 
    int poids; 
};
 
struct Sit{
    int node; 
    int nbDiv; 
    double dis; 
    bool operator <(const Sit &other) const{
        return dis > other.dis; 
    }
};
 
vector<Arc> adj[MAXI_NOEUDS]; 
int zerosAccess[MAXI_NOEUDS];  
int dejaVu[MAXI_NOEUDS]; 
 
void dfs(int n){
    if(dejaVu[n] == 1)
        return; 
    if(n == fin){
        finAccess = true; 
        return;
    } 
    if(pouvoirs[n] == 0)
        zerosAccess[n] = 1;
        
    dejaVu[n] = 1; 
    for(int v=0; v<adj[n].size(); v++){
        dfs(adj[n][v].dest); 
    }
}
 
priority_queue<Sit> aTraiter; 
 
int deja[MAXI_NOEUDS][MAXI_K]; 
 
double djikstra(){
    aTraiter.push({fin, 0, 0});
    for(int j=0; j<MAXI_K; j++){
        deja[fin][j] = 1; 
    }
    while(!aTraiter.empty()){
        Sit curSit = aTraiter.top(); 
        //cout << curSit.node << endl;
        aTraiter.pop(); 
        if(zerosAccess[curSit.node] == 1){
            return curSit.dis; 
        }
        deja[curSit.node][curSit.nbDiv] = 1;
        for(int v=0; v<adj[curSit.node].size(); v++){
            Arc voisin = adj[curSit.node][v];
            //cout << curSit.node << " : " << voisin.dest << endl;
            if(!deja[voisin.dest][curSit.nbDiv])
                aTraiter.push({voisin.dest, curSit.nbDiv, curSit.dis + (double)voisin.poids/(double)pow(2, curSit.nbDiv)});
            if(pouvoirs[curSit.node] == 2 && curSit.nbDiv < K){
                if(!deja[voisin.dest][curSit.nbDiv+1])
                    aTraiter.push({voisin.dest, curSit.nbDiv+1, curSit.dis + (double)voisin.poids/(double)pow(2, curSit.nbDiv+1)});
            }
                
        }
        
 
    }
    return -1; 
}
 
double solve(int N, int M, int k, int H, vector<int> u, vector<int> v, vector<int> c, vector<int> arr) {
    
    pouvoirs.clear(); 
    finAccess = false; 
    while(!aTraiter.empty()){
        aTraiter.pop(); 
    }
    for(int i=0; i<MAXI_NOEUDS; i++){
        adj[i].clear(); 
        zerosAccess[i] = 0; 
        dejaVu[i] = 0; 
        for(int j=0; j<MAXI_K; j++){
            deja[i][j] = 0;
        }
 
    }
    zerosAccess[0] = 1;
    pouvoirs = arr; 
    fin = H;
    nbNoeuds = N; 
    nbAretes = M;  
    K = min(k, MAXI_K);
    for(int n=0; n<M; n++){
        adj[u[n]].push_back({v[n], c[n]}); 
        adj[v[n]].push_back({u[n], c[n]}); 
    }
    dfs(0); 
 
    if(!finAccess)
        return -1; 
    else
        return djikstra(); 
}

Compilation message (stderr)

cyberland.cpp: In function 'void dfs(int)':
cyberland.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Arc>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int v=0; v<adj[n].size(); v++){
      |                  ~^~~~~~~~~~~~~~
cyberland.cpp: In function 'double djikstra()':
cyberland.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Arc>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int v=0; v<adj[curSit.node].size(); v++){
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~

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