#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150010;
const int INF = 2000000000;
int beaulty[MAXN][2];
int ar[2 * MAXN], in[2 * MAXN], dist[2][2 * MAXN], marc[2 * MAXN], mod[2][2 * MAXN];
vector<int> rev[2 * MAXN];
int cycleSize[2];
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();
getCycle();
bfs(P);
// for(int i = 0; i < N; i++){
// printf("%d %d\n", dist[0][2 * i], dist[1][2 * i]);
// }
for(int i = 0; i < Q; i++){
int ans = 0;
for(int j = 0; j < N; j++){
if(dist[0][2 * j] != -1)
if(dist[0][2 * j] <= G[i] && dist[0][2 * j] % mod[0][2 * j] == G[i] % mod[0][2 * j]) ans++;
if(dist[1][2 * j] != -1)
if(dist[1][2 * j] <= G[i] && dist[1][2 * j] % mod[1][2 * j] == G[i] % mod[1][2 * j]) ans++;
}
answer(ans);
}
}
void bfs(int ini){
queue<int> fila;
for(int i = 0; i < n; i++){
dist[0][2 * i] = -1;
dist[0][2 * i + 1] = -1;
dist[1][2 * i] = -1;
dist[1][2 * i + 1] = -1;
}
dist[0][2 * ini] = 0;
mod[0][2 * ini] = cycleSize[0];
fila.push(2 * ini);
while(!fila.empty()){
int cur = fila.front();
fila.pop();
for(int i = 0; i < rev[cur].size(); i++){
int viz = rev[cur][i];
if(dist[0][viz] != -1) continue;
fila.push(viz);
dist[0][viz] = dist[0][cur] + 1;
mod[0][viz] = mod[0][cur];
}
}
dist[1][2 * ini + 1] = 0;
mod[1][2 * ini + 1] = cycleSize[1];
fila.push(2 * ini + 1);
while(!fila.empty()){
int cur = fila.front();
fila.pop();
for(int i = 0; i < rev[cur].size(); i++){
int viz = rev[cur][i];
if(dist[1][viz] != -1) continue;
fila.push(viz);
dist[1][viz] = dist[1][cur] + 1;
mod[1][viz] = mod[1][cur];
}
}
}
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[2 * p + 1]){
int cur = 2 * p + 1;
while(marc[cur] == 0){
marc[cur] = 1;
cycleSize[1]++;
cur = ar[cur];
}
}
else cycleSize[1] = INF;
if(!marc[2 * p]){
int cur = 2 * p;
while(marc[cur] == 0){
marc[cur] = 1;
cycleSize[0]++;
cur = ar[cur];
}
}
else cycleSize[0] = INF;
}
Compilation message
garden.cpp: In function 'void bfs(int)':
garden.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rev[cur].size(); i++){
~~^~~~~~~~~~~~~~~~~
garden.cpp:111: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 |
9 ms |
7552 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7476 KB |
Output is correct |
| 6 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7680 KB |
Output is correct |
| # |
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 |
9 ms |
7552 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7476 KB |
Output is correct |
| 6 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7680 KB |
Output is correct |
| 10 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 11 |
Correct |
18 ms |
9728 KB |
Output is correct |
| 12 |
Correct |
31 ms |
11384 KB |
Output is correct |
| 13 |
Incorrect |
50 ms |
18808 KB |
Output isn't correct |
| 14 |
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 |
9 ms |
7552 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7476 KB |
Output is correct |
| 6 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
9 ms |
7552 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7680 KB |
Output is correct |
| 10 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 11 |
Correct |
18 ms |
9728 KB |
Output is correct |
| 12 |
Correct |
31 ms |
11384 KB |
Output is correct |
| 13 |
Incorrect |
50 ms |
18808 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
