#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 150005
int p;
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 = ok0 = ok1 = 0;
while(!st.empty()) {
t = st.top(); st.pop();
// printf("%d ",t);
cnt++;
if(t==p) ok0 = 1;
if(t==p+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;
p = P;
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;
// printf("edge %d(%d) => %d(%d)\n",x,0,from[x*2]/2,from[x*2]%2);
// printf("edge %d(%d) => %d(%d)\n",x,1,from[x*2+1]/2,from[x*2+1]%2);
}
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;
len[p*2][0] = 0;
dfs2(p*2,0);
len[p*2+1][1] = 0;
dfs2(p*2+1,1);
// printf("sz0 = %d sz1 = %d\n",sz0,sz1);
// for(x=0;x<2*N;x++) printf("len %d 0 = %d len %d 1 = %d\n",x,len[x][0],x,len[x][1]);
for(i=0;i<Q;i++) {
res = 0;
for(x=1;x<2*N;x+=2) {
if(len[x][0]!=-1 && G[i]==len[x][0]) res++;
else if(len[x][1]!=-1 && G[i]==len[x][1]) res++;
else if(sz0 && len[x][0]!=-1 && (G[i]-len[x][0])%sz0==0) res++;
else if(sz1 && len[x][1]!=-1 && (G[i]-len[x][1])%sz1==0) res++;
}
answer(res);
}
}
Compilation message
garden.cpp: In function 'void dfs2(int, int)':
garden.cpp:44: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 |
13 ms |
11072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
11072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
11072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
