#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_M 1000000
#define MAX_Q 2000
static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&P));
for(i=0; i<M; i++)
my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
my_assert(1==scanf("%d",&Q));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&G[i]));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&solutions[i]));
}
void answer(int x)
{
if(answer_count>=Q) {
printf("Incorrect. Too many answers.\n");
exit(0);
}
answers[answer_count] = x;
answer_count++;
}
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=15e4+6;
const int INF=1e9;
bool ending[2*MAXN];
int nxt[2*MAXN];
vector<pair<int,int> >edges;
vector<pair<int,int> >g[MAXN];
int dist[2*MAXN];
int which[2*MAXN];
vector<int>rev[MAXN];
int cnt[3*MAXN];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++)
{
R[i][0]++;
R[i][1]++;
}
//for(int i=0;i<Q;i++)G[i]++;
P++;
for(int i=0;i<M;i++)
{
if(R[i][1]==P)
{
//cout<<" - "<<2*i<<endl;
ending[2*i]=1;
}
edges.push_back({R[i][0],R[i][1]});
if(R[i][0]==P)
{
//cout<<" - "<<2*i+1<<endl;
ending[2*i+1]=1;
}
edges.push_back({R[i][1],R[i][0]});
g[R[i][0]].push_back({R[i][1],2*i});
g[R[i][1]].push_back({R[i][0],2*i+1});
}
for(int i=0;i<edges.size();i++)
{
if(g[edges[i].second].size()==1)
{
nxt[i]=g[edges[i].second][0].second;
}
else if(g[edges[i].second][0].first==edges[i].first)
{
nxt[i]=g[edges[i].second][1].second;
}
else
{
nxt[i]=g[edges[i].second][0].second;
}
rev[nxt[i]].push_back(i);
}
queue<int>q;
for(int i=0;i<edges.size();i++)
{
dist[i]=INF;
if(ending[i]==1)
{
//cout<<" "<<i<<endl;
q.push(i);
dist[i]=1;
which[i]=i;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto xd:rev[u])
{
if(dist[xd]!=INF)continue;
dist[xd]=dist[u]+1;
which[xd]=which[u];
q.push(xd);
}
}
int cycle_size=-1;
for(int i=0;i<edges.size();i++)
{
if(dist[i]==1)
{
//cout<<edges[i].first<<" "<<edges[i].second<<" "<<dist[i]<<endl;
if(dist[nxt[i]]==INF)continue;
cycle_size=dist[nxt[i]]+1;
}
}
for(int i=1;i<=N;i++)
{
int e=g[i][0].second;
if(dist[e]!=INF)
{
cnt[dist[e]]++;
}
}
if(cycle_size!=-1)for(int i=cycle_size;i<3*MAXN;i++)cnt[i]+=cnt[i-cycle_size];
for(int i=0;i<Q;i++)
{
if(G[i]<3*MAXN)answer(cnt[G[i]]);
else if(cycle_size==-1)answer(0);
else
{
int k=(G[i]-3*MAXN)/cycle_size+1;
k=G[i]-k*cycle_size;
answer(cnt[k]);
}
}
}
int main()
{
int correct, i;
read_input();
answer_count = 0;
count_routes(N,M,P,R,Q,G);
if(answer_count!=Q) {
printf("Incorrect. Too few answers.\n");
exit(0);
}
correct = 1;
for(i=0; i<Q; i++)
if(answers[i]!=solutions[i])
correct = 0;
if(correct)
printf("Correct.\n");
else {
printf("Incorrect.\n");
printf("Expected: ");
for(i=0; i<Q; i++)
printf("%d ",solutions[i]);
printf("\nReturned: ");
for(i=0; i<Q; i++)
printf("%d ",answers[i]);
}
return 0;
}
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2
*/
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
garden.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
garden.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i=0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccx0sTCT.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccJjIShW.o:garden.cpp:(.text+0xa0): first defined here
/usr/bin/ld: /tmp/ccx0sTCT.o: in function `answer(int)':
grader.cpp:(.text+0x130): multiple definition of `answer(int)'; /tmp/ccJjIShW.o:garden.cpp:(.text+0x1d0): first defined here
/usr/bin/ld: /tmp/ccx0sTCT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJjIShW.o:garden.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
