#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150010;
int beaulty[MAXN][2];
int ar[2 * MAXN], in[2 * MAXN], dist[2 * MAXN], marc[2 * MAXN];
vector<int> rev[2 * MAXN];
int cycleSize;
int n, p;
void bfs(int ini);
void getCycle();
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
p = P;
n = N;
for(int i = 0; i < N; i++){
ar[2 * i] = -1;
ar[2 * i + 1] = -1;
}
for(int i = 0; i < M; i++){
if(ar[2 * R[i][0]] == -1) ar[2 * R[i][0]] = i, beaulty[i][0] = 1;
else if(ar[2 * R[i][0] + 1] == -1) ar[2 * R[i][0] + 1] = i, beaulty[i][0] = 2;
if(ar[2 * R[i][1]] == -1) ar[2 * R[i][1]] = i, beaulty[i][1] = 1;
else if(ar[2 * R[i][1] + 1] == -1) ar[2 * R[i][1] + 1] = i, beaulty[i][1] = 2;
}
for(int i = 0; i < M; i++){
// printf("%d -- %d (%d)\n", R[i][0], R[i][1], i);
// printf("%d -- %d\n", beaulty[i][0], beaulty[i][1]);
if(beaulty[i][0] == 1 && beaulty[i][1] == 1){
ar[2 * R[i][0]] = 2 * R[i][1] + 1;
ar[2 * R[i][1]] = 2 * R[i][0] + 1;
}
else if(beaulty[i][0] == 2 && beaulty[i][1] == 1){
ar[2 * R[i][0] + 1] = 2 * R[i][1] + 1;
ar[2 * R[i][1]] = 2 * R[i][0];
}
else if(beaulty[i][0] == 1 && beaulty[i][1] == 2){
ar[2 * R[i][0]] = 2 * R[i][1];
ar[2 * R[i][1] + 1] = 2 * R[i][0] + 1;
}
else{
if(beaulty[i][0] > 0)
ar[2 * R[i][0] + (beaulty[i][0]) - 1] = 2 * R[i][1];
if(beaulty[i][1] > 0)
ar[2 * R[i][1] + (beaulty[i][1]) - 1] = 2 * R[i][0];
}
}
for(int i = 0; i < N; i++){
if(ar[2 * i] == -1)
ar[2 * i] = ar[2 * i + 1];
if(ar[2 * i + 1] == -1)
ar[2 * i + 1] = ar[2 * i];
}
for(int i = 0; i < N; i++){
rev[ar[2 * i]].push_back(2 * i);
rev[ar[2 * i + 1]].push_back(2 * i + 1);
}
for(int i = 0; i < N; i++)
in[2 * i] = rev[2 * i].size(), in[2 * i + 1] = rev[2 * i + 1].size();
for(int i = 0; i < N; i++){
// printf("%d.0 %d.%d\n%d.1 %d.%d\n", i, ar[2 * i] / 2, ar[2 * i] % 2, i, ar[2 * i + 1] / 2, ar[2 * i + 1] % 2);
}
getCycle();
bfs(P);
//printf("\n");
for(int i = 0; i < Q; i++){
int ans = 0;
for(int j = 0; j < N; j++){
if(dist[2 * j] == -1) continue;
if(dist[2 * j] <= G[i] && dist[2 * j] % cycleSize == G[i] % cycleSize) ans++;
}
answer(ans);
}
}
void bfs(int ini){
queue<int> fila;
for(int i = 0; i < n; i++){
dist[2 * i] = -1;
dist[2 * i + 1] = -1;
}
dist[2 * ini] = 0;
dist[2 * ini + 1] = 0;
fila.push(2 * ini);
fila.push(2 * ini + 1);
while(!fila.empty()){
int cur = fila.front();
// printf("\t%d.%d\n", cur / 2, cur % 2);
fila.pop();
for(int i = 0; i < rev[cur].size(); i++){
int viz = rev[cur][i];
if(dist[viz] != -1) continue;
fila.push(viz);
dist[viz] = dist[cur] + 1;
}
}
}
void getCycle(){
queue<int> fila;
for(int i = 0; i < n; i++){
if(in[2 * i] == 0) fila.push(2 * i);
if(in[2 * i + 1] == 0) fila.push(2 * i + 1);
}
while(!fila.empty()){
int cur = fila.front();
marc[cur] = 1;
fila.pop();
int viz = ar[cur];
if(marc[viz]) continue;
in[viz]--;
if(in[viz] == 0) fila.push(viz);
}
if(marc[p]){
cycleSize = 10 * MAXN;
return;
}
int cur = p;
while(marc[cur] == 0){
marc[cur] = 1;
cycleSize++;
cur = ar[cur];
}
}
Compilation message
garden.cpp: In function 'void bfs(int)':
garden.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rev[cur].size(); i++){
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
