#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);
}
}
Compilation message
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)
~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
