제출 #167274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167274		L01	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	23 ms	22876 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<queue>
using namespace std;
int nodoorig[800005],ninicio[150005],tnodos,entradaprim[150005],entradasec[150005],salidaprim[150005],salidasec[150005],siguiente[800005],distancia[800005],nodotermino[800005],vis[800005],numvis,origen,iniciclo[800005],longitudciclo[800005],nodofinal;
vector<int>anterior[800005],entrdasafin,entradasantesciclo[150005];
queue<int>cola;
int creanodo(int original)
{
    nodoorig[++tnodos]=original;
    return tnodos;
}
void unir(int n1,int n2)
{
    siguiente[n1]=n2;
    anterior[n2].push_back(n1);
}
void desunir(int n1,int n2)
{
    siguiente[n1]=0;
    anterior[n2].pop_back();
}
void calculadistancias()
{
    while(!cola.empty())
    {
        int nodoact=cola.front();
        cola.pop();
        if(vis[nodoact]!=numvis)
        {
            vis[nodoact]=numvis;
            for(int i=0;i<anterior[nodoact].size();i++)
            {
                cola.push(anterior[nodoact][i]);
                distancia[anterior[nodoact][i]]=distancia[nodoact]+1;
                nodotermino[anterior[nodoact][i]]=nodotermino[nodoact];
            }
        }
    }
}
void recorreciclo(int nodo,int distancia)
{
    if(vis[nodo]!=numvis)
    {
        vis[nodo]=numvis;
        if(nodoorig[nodo]==nodofinal)
        {
            entradasantesciclo[origen].push_back(nodo);
            entradasantesciclo[origen].push_back(distancia);
        }
        recorreciclo(nodo,distancia+1);
    }
    else
    {
        if(nodoorig[nodo]==nodofinal)
        {
            for(int i=0;i<entradasantesciclo[origen].size();i+=2)
            {
                if(entradasantesciclo[origen][i]==nodo)
                {
                    iniciclo[origen]=i;
                    longitudciclo[origen]=distancia-entradasantesciclo[origen][i+1]+1;
                }
            }
        }
    }
}
void calculaciclos()
{
    for(int inicio:entrdasafin)
    {
        numvis++;
        origen=inicio;
        recorreciclo(origen,0);
    }
}
void count_routes(int tnodoso,int taristaso,int restaurant,int aristaso[150005][2],int tcasos,int largocamino[2003])
{
    nodofinal=restaurant;
    for(int i=0;i<taristaso;i++)
    {
        int extremo1=aristaso[i][0],extremo2=aristaso[i][1],entradae1=0,entradae2=0;
        if(ninicio[extremo1]==0)
            ninicio[extremo1]=creanodo(extremo1);
        if(ninicio[extremo2]==0)
            ninicio[extremo2]=creanodo(extremo2);
        if(salidaprim[extremo1]==0)
        {
            salidaprim[extremo1]=creanodo(extremo1);
            entradaprim[extremo1]=creanodo(extremo1);
            if(extremo1==nodofinal)
                entrdasafin.push_back(entradaprim[extremo1]);
            unir(ninicio[extremo1],salidaprim[extremo1]);
            unir(entradaprim[extremo1],salidaprim[extremo1]);
        }
        else
        {
            if(salidasec[extremo1]==0)
            {
                salidasec[extremo1]=creanodo(extremo1);
                entradasec[extremo1]=creanodo(extremo1);
                if(extremo1==nodofinal)
                    entrdasafin.push_back(entradasec[extremo1]);
                desunir(entradaprim[extremo1],salidaprim[extremo1]);
                unir(entradaprim[extremo1],salidasec[extremo1]);
                unir(entradasec[extremo1],salidaprim[extremo1]);
            }
            else
            {
                entradae1=creanodo(extremo1);
                if(extremo1==nodofinal)
                    entrdasafin.push_back(entradae1);
                unir(entradae1,salidaprim[extremo1]);
            }
        }
        if(salidaprim[extremo2]==0)
        {
            salidaprim[extremo2]=creanodo(extremo2);
            entradaprim[extremo2]=creanodo(extremo2);
            if(extremo2==nodofinal)
                entrdasafin.push_back(entradaprim[extremo2]);
            unir(ninicio[extremo2],salidaprim[extremo2]);
            unir(entradaprim[extremo2],salidaprim[extremo2]);
        }
        else
        {
            if(salidasec[extremo2]==0)
            {
                salidasec[extremo2]=creanodo(extremo2);
                entradasec[extremo2]=creanodo(extremo2);
                if(extremo2==nodofinal)
                    entrdasafin.push_back(entradasec[extremo2]);
                desunir(entradaprim[extremo2],salidaprim[extremo2]);
                unir(entradaprim[extremo2],salidasec[extremo2]);
                unir(entradasec[extremo2],salidaprim[extremo2]);
            }
            else
            {
                entradae2=creanodo(extremo2);
                if(extremo2==nodofinal)
                    entrdasafin.push_back(entradae2);
                unir(entradae2,salidaprim[extremo2]);
            }
        }
        if(salidasec[extremo1]==0)
        {
            if(salidasec[extremo2]==0)
            {
                unir(salidaprim[extremo1],entradaprim[extremo2]);
                unir(salidaprim[extremo2],entradaprim[extremo1]);
            }
            else
            {
                if(entradae2==0)
                {
                    unir(salidaprim[extremo1],entradasec[extremo2]);
                    unir(salidasec[extremo2],entradaprim[extremo1]);
                }
                else
                {
                    unir(salidaprim[extremo1],entradae2);
                }
            }
        }
        else
        {
            if(entradae1==0)
            {
                if(salidasec[extremo2]==0)
                {
                    unir(salidasec[extremo1],entradaprim[extremo2]);
                    unir(salidaprim[extremo2],entradasec[extremo1]);
                }
                else
                {
                    if(entradae2==0)
                    {
                        unir(salidasec[extremo1],entradasec[extremo2]);
                        unir(salidasec[extremo2],entradasec[extremo1]);
                    }
                    else
                    {
                        unir(salidasec[extremo1],entradae2);
                    }
                }
            }
            else
            {
                if(salidasec[extremo2]==0)
                {
                    unir(salidaprim[extremo2],entradae1);
                }
                else
                {
                    if(entradae2==0)
                    {
                        unir(salidasec[extremo2],entradae1);
                    }
                }
            }
        }
    }
    for(int inicio:entrdasafin)
    {
        vis[inicio]=true;
        nodotermino[inicio]=inicio;
        for(int i=0;i<anterior[inicio].size();i++)
        {
            cola.push(anterior[inicio][i]);
            distancia[anterior[inicio][i]]=1;
            nodotermino[anterior[inicio][i]]=inicio;
        }
    }
    numvis++;
    calculadistancias();
    calculaciclos();
    for(int i=0;i<tcasos;i++)
    {
        int tformas=0;
        for(int j=0;j<tnodoso;j++)
        {
            if(2*largocamino[i]==distancia[ninicio[j]])
                tformas++;
            else
            {
                if(largocamino[i]>distancia[ninicio[j]])
                {
                    int dist=distancia[ninicio[j]],nciclo=nodotermino[ninicio[j]];
                    for(int k=1;k<entradasantesciclo[nciclo].size();k+=2)
                    {
                        if(dist+entradasantesciclo[nciclo][k]==2*largocamino[i])
                            tformas++;
                    }
                    if(longitudciclo[nciclo]>0)
                    {
                        for(int k=iniciclo[nciclo]+1;k<entradasantesciclo[nciclo].size();k+=2)
                        {
                            int drecorridaciclo=2*largocamino[i]-dist-entradasantesciclo[nciclo][k];
                            if(drecorridaciclo%longitudciclo[nciclo]==0 and drecorridaciclo%longitudciclo[nciclo]>0)
                                tformas++;
                        }
                    }
                }
            }
        }
        answer(tformas);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void calculadistancias()':
garden.cpp:33:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<anterior[nodoact].size();i++)
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void recorreciclo(int, int)':
garden.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<entradasantesciclo[origen].size();i+=2)
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:208:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<anterior[inicio].size();i++)
                     ~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:230:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int k=1;k<entradasantesciclo[nciclo].size();k+=2)
                                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:237:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int k=iniciclo[nciclo]+1;k<entradasantesciclo[nciclo].size();k+=2)
                                                      ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31