oj.uz

Submission #1016204

# Submission time Handle Problem Language Result Execution time Memory
1016204 2024-07-07T13:54:26 Z nomen_nescio Cyberland (APIO23_cyberland) C++17
0 / 100
 650 ms 1037300 KB 
#include "cyberland.h"

#include <vector>
#include <queue>
#include <cmath>

struct Noeud
{
    int index, poids;
};

struct Chemin
{
    double somme;
    int iNoeud, nbDivPris;

    bool operator< (const Chemin &autre) const
    {
        return somme > autre.somme;
    }
};

const int MAX_NOEUDS = 1e5;

std::vector<Noeud> voisins[MAX_NOEUDS];
int nbNoeuds, noeudArrivee, nbDivMax;
int type[MAX_NOEUDS];

bool zeroAccessible[MAX_NOEUDS];

double dijkstra()
{
    bool estPasse[nbNoeuds][nbDivMax];for (int i = 0; i < nbNoeuds; i++) for (int j = 0; j < nbNoeuds; j++) estPasse[i][j] = false;

    std::priority_queue<Chemin> aPasser;
    aPasser.push({0, noeudArrivee, 0});
    while (aPasser.size() != 0)
    {
        Chemin cheminCourant = aPasser.top();
        aPasser.pop();
        
        {
            estPasse[cheminCourant.iNoeud][cheminCourant.nbDivPris] = true;
            if (zeroAccessible[cheminCourant.iNoeud])
            {
                return cheminCourant.somme;
            }
            
            double somme = cheminCourant.somme;
            // on ajoute les voisins
            for (int iVoisin = 0; iVoisin < voisins[cheminCourant.iNoeud].size(); iVoisin++)
            {
                double nouvelleSomme;
                int voisin = voisins[cheminCourant.iNoeud][iVoisin].index;

                nouvelleSomme = somme + voisins[cheminCourant.iNoeud][iVoisin].poids / pow(2, cheminCourant.nbDivPris);


                // on le fait en prennant ou non la division si possible
                if (!estPasse[voisin][cheminCourant.nbDivPris])
                {
                    estPasse[voisin][cheminCourant.nbDivPris] = true;
                    aPasser.push({nouvelleSomme, voisin, cheminCourant.nbDivPris});
                }
                if (!estPasse[voisin][cheminCourant.nbDivPris+1] && type[voisin] == 2 && cheminCourant.nbDivPris < nbDivMax)
                {
                    estPasse[voisin][cheminCourant.nbDivPris+1] = true;
                    aPasser.push({nouvelleSomme, voisin, cheminCourant.nbDivPris+1});
                } 
            }
        }
    }

    return -1;
}




double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{
    nbNoeuds = N;
    noeudArrivee = H;
    nbDivMax = K;
    for (int i = 0; i < M; i++)
    {
        voisins[x[i]].push_back({y[i], c[i]});
        voisins[y[i]].push_back({x[i], c[i]});
    }

    for (int i = 0; i < nbNoeuds; i++)
    {
        type[i] = arr[i];
    }

    // on fait un bfs pour savoir quelles cases qui mettent 0 sont accessibles
    
    
    std::queue<int> aPasser;
    bool estPasse[nbNoeuds]; for (int i = 0; i < nbNoeuds; i++)estPasse[i] = false;
    aPasser.push(0);
    while (aPasser.size() != 0)
    {
        int iCourant = aPasser.front();
        aPasser.pop();

        if (!estPasse[iCourant] && iCourant != H)
        {
            if (type[iCourant] == 0)
            {
                zeroAccessible[iCourant] = true;
            }
            estPasse[iCourant] = true;
            for (int iVoisin = 0; iVoisin < voisins[iCourant].size(); iVoisin++)
            {
                aPasser.push(voisins[iCourant][iVoisin].index);
            }
        }
    }

    zeroAccessible[0] = true;

    return dijkstra();
}

Compilation message

cyberland.cpp: In function 'double dijkstra()':
cyberland.cpp:51:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Noeud>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int iVoisin = 0; iVoisin < voisins[cheminCourant.iNoeud].size(); iVoisin++)
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:114:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Noeud>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int iVoisin = 0; iVoisin < voisins[iCourant].size(); iVoisin++)
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6068 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 17064 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6184 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5952 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

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