oj.uz

Submission #1016214

# Submission time Handle Problem Language Result Execution time Memory
1016214 2024-07-07T14:00:35 Z nam6 Cyberland (APIO23_cyberland) C++17
0 / 100
 42 ms 62556 KB 
#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<N; 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 62300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 62544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 62444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35420 KB Correct.
2 Runtime error 42 ms 62548 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 62552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 62556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 62556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 62548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -