Submission #1016204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016204		nomen_nescio	Cyberland (APIO23_cyberland)	C++17	0 / 100	650 ms	1037300 KiB

cyberland

#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 (stderr)

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 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3