This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "garden.h"
#include "gardenlib.h"
#include<vector>
using namespace std;
#define MAXN 151000
vector<int> connexion[MAXN];
int destination[2*MAXN];
vector<int> revdest[2*MAXN];
int dist1[2*MAXN];
int dist2[2*MAXN];
bool vst1[2*MAXN];
bool vst2[2*MAXN];
int incycle1=0;
int incycle2=0;
int PP,NN;
void dfs1(int i,int l)
{
if(i==PP && vst1[i]) incycle1=l;
if(vst1[i]) return ;
vst1[i]=true;
dist1[i]=l;
for(int x=0;x<revdest[i].size();x++)
dfs1(revdest[i][x],l+1);
return;
}
void dfs2(int i,int l)
{
if(i==PP+NN && vst2[i]) incycle2=l;
if(vst2[i]) return;
vst2[i]=true;
dist2[i]=l;
for(int x=0;x<revdest[i].size();x++)
dfs2(revdest[i][x],l+1);
return;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
NN=N;
PP=P;
for(int i=0;i<M;i++)
{
connexion[R[i][0]].push_back(R[i][1]);
connexion[R[i][1]].push_back(R[i][0]);
}
for(int i=0;i<N;i++)
{
destination[i+N]=destination[i]=connexion[i][0];
if(connexion[i].size()!=1)
destination[i+N]=connexion[i][1];
}
for(int i=0;i<2*N;i++)
{
if(connexion[destination[i]][0]==i%N)
revdest[destination[i]+N].push_back(i);
else
revdest[destination[i]].push_back(i);
}
dfs1(P,0);
dfs2(P+N,0);
/*
for(int i=0;i<2*N;i++) printf("%d ",dist1[i]);
printf("%d ",incycle1);
puts("");
for(int i=0;i<2*N;i++) printf("%d ",dist2[i]);
printf("%d ",incycle2);
*/
for(int i=0;i<Q;i++)
{
int cnt=0;
for(int j=0;j<N;j++)
{
if(G[i]>=dist1[j] && vst1[j])
{
if(incycle1==0)
{
if(G[i]==dist1[j])
{
cnt++;
continue;
}
}
else
if( (G[i]-dist1[j])%incycle1==0 )
{
cnt++;
continue;
}
}
if(G[i]>=dist2[j] && vst2[j])
{
if(incycle2==0)
{
if(G[i]==dist2[j])
cnt++;
}
else
if( (G[i]-dist2[j])%incycle2==0 )
cnt++;
}
}
answer(cnt);
}
/*
for(int i=0;i<2*N;i++)
{
fprintf(stderr,"\n%d",revdest[i].size());
for(int j=0;j<revdest[i].size();j++)
fprintf(stderr," %d",revdest[i][j]);
}
*/
return;
}
Compilation message (stderr)
garden.cpp: In function 'void dfs1(int, int)':
garden.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0;x<revdest[i].size();x++)
~^~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void dfs2(int, int)':
garden.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0;x<revdest[i].size();x++)
~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |