#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,bool>d[150000][2];
int dis[150000][2],DIS[150000][2];
vector<pair<int,bool>>r[150000][2];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
for(int i=0;i<N;i++){
d[i][0]=d[i][1]={-1,0};
}
for(int i=0;i<M;i++){
int p=R[i][0];
int q=R[i][1];
if(d[p][0].first==-1){
d[p][0].first=q;
}
else if(d[p][1].first==-1){
d[p][1].first=q;
}
swap(p,q);
if(d[p][0].first==-1){
d[p][0].first=q;
}
else if(d[p][1].first==-1){
d[p][1].first=q;
}
}
for(int i=0;i<N;i++){
if(d[d[i][0].first][0].first==i){
d[i][0].second=true;
}
if(d[i][1].first==-1){
d[i][1].first=d[i][0].first;
}
if(d[d[i][1].first][0].first==i){
d[i][1].second=true;
}
r[d[i][0].first][d[i][0].second].push_back({i,0});
r[d[i][1].first][d[i][1].second].push_back({i,1});
}
queue<pair<int,bool>>q;
q.push({P,0});
q.push({-1,0});
int dd=0;
while(q.size()>=2){
auto p=q.front();
q.pop();
if(p==pair<int,bool>{-1,0}){
dd++;
q.push({-1,0});
continue;
}
if(dis[p.first][p.second])continue;
dis[p.first][p.second]=dd;
for(auto pp:r[p.first][p.second]){
q.push(pp);
}
}
queue<pair<int,bool>>qq;
swap(q,qq);
dd=0;
q.push({P,1});
q.push({-1,0});
while(q.size()>=2){
auto p=q.front();
q.pop();
if(p==pair<int,bool>{-1,0}){
dd++;
q.push({-1,0});
continue;
}
if(DIS[p.first][p.second])continue;
DIS[p.first][p.second]=dd;
for(auto pp:r[p.first][p.second]){
q.push(pp);
}
}
for(int i=0;i<Q;i++){
int c=0;
for(int j=0;j<N;j++){
if(dis[j][0]==G[i]||(dis[j][0]<G[i]&&dis[P][0]&&(G[i]-dis[j][0])%dis[P][0]==0)||DIS[j][0]==G[i]||(DIS[j][0]<G[i]&&DIS[P][1]&&(G[i]-DIS[j][0])%DIS[P][1]==0)){
c++;
}
}
answer(c);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
