#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 150005
int sz0,sz1;
int from[maxn*2];
int vis[maxn*2];
int len[maxn*2][2];
vector<int> mn[maxn];
vector<int> re[maxn*2];
stack<int> st;
void dfs(int x,int last) {
int t,cnt,ok0,ok1;
if(vis[x]==1) {
// printf("cycle ");
cnt = 0;
while(!st.empty()) {
t = st.top(); st.pop();
// printf("%d ",t);
cnt++;
if(t==0) ok0 = 1;
if(t==1) ok1 = 1;
if(t==x) break;
}
if(ok0) sz0 = cnt;
if(ok1) sz1 = cnt;
// printf("\n");
return ;
}
vis[x] = 1;
st.push(x);
if(vis[from[x]]<=1) dfs(from[x],x);
vis[x] = 2;
if(!st.empty()) st.pop();
}
void dfs2(int x,int now) {
int i,y;
for(i=0;i<re[x].size();i++) {
y = re[x][i];
if(len[y][now]==-1) {
len[y][now] = len[x][now] + 1;
dfs2(y,now);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
int i,x,y,res;
for(i=0;i<M;i++) {
x = R[i][0]; y = R[i][1];
if(mn[x].size()<2) mn[x].push_back(y);
if(mn[y].size()<2) mn[y].push_back(x);
}
for(x=0;x<N;x++) if(mn[x].size()<2) mn[x].push_back(mn[x][0]);
for(x=0;x<N;x++) {
y = mn[x][1];
if(mn[y][0]==x) from[x*2] = y*2;
else from[x*2] = y*2+1;
y = mn[x][0];
if(mn[y][0]==x) from[x*2+1] = y*2;
else from[x*2+1] = y*2+1;
}
for(x=0;x<2*N;x++) re[from[x]].push_back(x);
for(x=0;x<N;x++) if(!vis[x*2]) dfs(x*2,-1);
for(x=0;x<2*N;x++) len[x][0] = len[x][1] = -1;
dfs2(0,0); dfs2(1,1);
for(i=0;i<Q;i++) {
res = 0;
for(x=0;x<2*N;x++) if((len[x][0]!=-1 && G[i]>=len[x][0] && (G[i]-len[x][0])%sz0==0) || (len[x][1]!=-1 && G[i]>=len[x][1] && (G[i]-len[x][1])%sz0==0)) res++;
answer(res);
}
}
Compilation message
garden.cpp: In function 'void dfs2(int, int)':
garden.cpp:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<re[x].size();i++) {
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
