oj.uz

Submission #1023239

# Submission time Handle Problem Language Result Execution time Memory
1023239 2024-07-14T13:54:34 Z nam6 Cyberland (APIO23_cyberland) C++17
92 / 100
 3000 ms 38096 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<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

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 Execution timed out 3023 ms 30960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 31056 KB Correct.
2 Correct 145 ms 31008 KB Correct.
3 Correct 118 ms 31056 KB Correct.
4 Correct 150 ms 31056 KB Correct.
5 Correct 131 ms 31032 KB Correct.
6 Correct 37 ms 31480 KB Correct.
7 Correct 54 ms 31572 KB Correct.
8 Correct 17 ms 32348 KB Correct.
9 Correct 1077 ms 30984 KB Correct.
10 Correct 1022 ms 31016 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31052 KB Correct.
2 Correct 132 ms 31060 KB Correct.
3 Correct 136 ms 31068 KB Correct.
4 Correct 1065 ms 31060 KB Correct.
5 Correct 998 ms 30808 KB Correct.
6 Correct 16 ms 31320 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35420 KB Correct.
2 Correct 131 ms 31068 KB Correct.
3 Correct 136 ms 31076 KB Correct.
4 Correct 133 ms 31320 KB Correct.
5 Correct 1096 ms 31056 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 31048 KB Correct.
2 Correct 142 ms 31100 KB Correct.
3 Correct 128 ms 31064 KB Correct.
4 Correct 43 ms 31836 KB Correct.
5 Correct 1178 ms 31008 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 31084 KB Correct.
2 Correct 137 ms 31104 KB Correct.
3 Correct 38 ms 36180 KB Correct.
4 Correct 34 ms 31564 KB Correct.
5 Correct 1153 ms 30812 KB Correct.
6 Correct 141 ms 31084 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 31068 KB Correct.
2 Correct 27 ms 31068 KB Correct.
3 Correct 44 ms 38096 KB Correct.
4 Correct 49 ms 32572 KB Correct.
5 Correct 39 ms 36636 KB Correct.
6 Correct 30 ms 35164 KB Correct.
7 Correct 62 ms 32604 KB Correct.
8 Correct 256 ms 31312 KB Correct.
9 Correct 160 ms 31436 KB Correct.
10 Correct 117 ms 31060 KB Correct.
11 Correct 602 ms 31056 KB Correct.
12 Correct 130 ms 31060 KB Correct.
13 Correct 132 ms 31044 KB Correct.
14 Correct 51 ms 34648 KB Correct.
15 Correct 92 ms 31824 KB Correct.
16 Correct 117 ms 31068 KB Correct.
17 Correct 121 ms 31064 KB Correct.
18 Correct 130 ms 31124 KB Correct.
19 Correct 135 ms 31068 KB Correct.
20 Correct 105 ms 30988 KB Correct.
21 Correct 22 ms 30812 KB Correct.
22 Correct 15 ms 31324 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 31108 KB Wrong Answer.
2 Halted 0 ms 0 KB -