#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 500005;
vector<pair<int,int>> temp[MAXN];
vector<int> adj[MAXN],rev[MAXN];
int dist[MAXN][2],disCovered[MAXN],step = 0,sccId[MAXN],sccNumber = 0;
vector<int> group[MAXN];
int chk[MAXN];
int getV(int x,int y){
if(temp[y].size() > 1 && temp[y][0].second == x) return 2 * y + 1;
return 2 * y;
}
void addEdge(int u,int v){
adj[u].push_back(v);
rev[v].push_back(u);
}
void bfs(int root){
queue<int> q;
for(int i=0;i<MAXN;i++)for(int j=0;j<2;j++) dist[i][j] = -1;
dist[root*2][0] = 0;
q.push(root*2);
while(!q.empty()){
int here = q.front(); q.pop();
for(auto x:rev[here]){
if(dist[x][0] == -1){ dist[x][0] = dist[here][0] + 1; q.push(x); }
}
}
dist[root*2+1][1] = 0;
q.push(root*2+1);
while(!q.empty()){
int here = q.front(); q.pop();
for(auto x:rev[here]){
if(dist[x][1] == -1){ dist[x][1] = dist[here][1] + 1; q.push(x); }
}
}
}
stack<int> st;
int dfs(int here){
int there;
st.push(here);
disCovered[here]=step++;
int ret=disCovered[here];
for(int i=0;i<adj[here].size();i++){
there=adj[here][i];
if(disCovered[there]==-1)
ret=min(dfs(there),ret);
else if(sccId[there]==-1)
ret=min(ret,disCovered[there]);
}
if(ret==disCovered[here]){
while(true){
int num=st.top();st.pop();
group[sccNumber].push_back(num);
sccId[num]=sccNumber;
if(num==here)
break;
}
step++;
}
return ret;
}
void dfsAll(int n){
memset(disCovered,-1,sizeof(disCovered));
for(int i=0; i < 2 * n;i++)
if(disCovered[i]==-1)
dfs(i);
}
//void answer(int cnt){
// cout<<cnt<<endl;
//}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++){
temp[R[i][0]].push_back({i,R[i][1]});
temp[R[i][1]].push_back({i,R[i][0]});
}
for(int i=0;i<N;i++){
sort(temp[i].begin(),temp[i].end());
}
for(int here=0;here<N;here++){
if(temp[here].size() == 0) continue;
int there = temp[here][0].second;
addEdge(2*here,getV(here,there));
there = (temp[here].size() > 1 ? temp[here][1].second : temp[here][0].second );
addEdge(2*here+1,getV(here,there));
}
dfsAll(N);
bfs(P);
for(int k=0;k<Q;k++){
int cnt = 0;
memset(chk,0,sizeof(chk));
for(int i=0;i<N;i++){
int bit = G[k];
if(dist[i*2][0] == -1 || dist[i*2][0] > bit) continue;
bit -= dist[i*2][0];
if(bit == 0) chk[i] = 1;
int id = sccId[2*P];
if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
chk[i] = 1;
}
}
for(int i=0;i<N;i++){
int bit = G[k];
if(dist[i*2][1] == -1 || dist[i*2][1] > bit) continue;
bit -= dist[i*2][1];
if(bit == 0) chk[i] = 1;
int id = sccId[2*P+1];
if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
chk[i] = 1;
}
}
for(int i=0;i<N;i++) cnt += chk[i];
answer(cnt);
}
}
Compilation message
garden.cpp: In function 'int dfs(int)':
garden.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[here].size();i++){
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
55336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
55336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
55336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
