#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;
priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;
int A[MAXN];
char S[MAXN];
int id[MAXN];
int iid[MAXN];
pii edge[MAXN];
bool chk[MAXN];
int dist[MAXN];
int D[MAXN];
int DD[MAXN];
inline void addedge(int x,int y,int idx){
if(chk[x]){
graph[(x<<1)].push_back(y);
}
else if(id[x]^idx){
graph[(x<<1)].push_back(y);
}
else {
graph[(x<<1)|1].push_back(y);
}
return;
}
int cyver = -1;
void dfs(int here){
int there;
for(int i=0;i<graph[here].size();i++){
there = graph[here][i];
if(dist[there]!=INF){
cyver = here;
continue;
}
dist[there] = dist[here]+1;
dfs(there);
}
return;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n = N;
int m = M;
int k = P;
int a,b;
int cur,idx = -1;
int cnt = 0;
for(int i=0;i<m;i++){
edge[i].f = R[i][0];
edge[i].s = R[i][1];
}
fill(id,id+n,-1);
fill(iid,iid+n,-1);
for(int i=m-1;i>=0;i--){
a = edge[i].f;
b = edge[i].s;
iid[a] = id[a];
id[a] = i;
iid[b] = id[b];
id[b] = i;
}
for(int i=0;i<n;i++){
chk[i] = (iid[i]==-1);
}
for(int i=0;i<n;i++){
idx = id[i];
a = edge[idx].f;
b = edge[idx].s;
if(a^i){
addedge(a,(i<<1),idx);
}
else {
addedge(b,(i<<1),idx);
}
if(chk[i])continue;
idx = iid[i];
a = edge[idx].f;
b = edge[idx].s;
if(a^i){
addedge(a,(i<<1)|1,idx);
}
else {
addedge(b,(i<<1)|1,idx);
}
}
/*
for(int i=0;i<(n<<1);i++){
cout<<i<<" ";
for(int j=0;j<(int)graph[i].size();j++){
cout<<graph[i][j]<<" ";
}
cout<<"\n";
}*/
int cy = -1;
int cyy = -1;
fill(dist,dist+(n<<1),INF);
dist[(k<<1)] = 0;
cyver = -1;
dfs((k<<1));
if(cyver==-1)cy = 0;
else cy = dist[cyver]+1;
for(int i=0;i<(n<<1);i++){
D[i] = dist[i];
}
//cout<<cy<<"\n";
/*
for(int i=0;i<(n<<1);i++){
cout<<D[i]<<" ";
}
cout<<"\n";*/
fill(dist,dist+(n<<1),INF);
dist[(k<<1)|1] = 0;
cyver = -1;
dfs((k<<1)|1);
if(cyver==-1)cyy = 0;
else cyy = dist[cyver]+1;
for(int i=0;i<(n<<1);i++){
DD[i] = dist[i];
}
/*
cout<<cyy<<"\n";
for(int i=0;i<(n<<1);i++){
cout<<DD[i]<<" ";
}
cout<<"\n";*/
int vv = 0;
for(int i=0;i<Q;i++){
vv = G[i];
cnt = 0;
for(int i=0;i<n;i++){
if(!cy){
if(D[(i<<1)]==k)cnt++;
}
else {
if(D[(i<<1)]<=k){
cur = (k-D[(i<<1)]);
if(!(cur%cy))cnt++;
}
}
if(!cyy){
if(DD[(i<<1)]==k)cnt++;
}
else {
if(DD[(i<<1)]<=k){
cur = (k-DD[(i<<1)]);
if(!(cur%cyy))cnt++;
}
}
}
answer(cnt);
}
return;
}
Compilation message
garden.cpp: In function 'void dfs(int)':
garden.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<graph[here].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:188:7: warning: variable 'vv' set but not used [-Wunused-but-set-variable]
188 | int vv = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
