#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, p, r[NMAX][2], q, g[NMAX], e[NMAX][2], a, b, d[NMAX], dd[NMAX], cy2, cy;
vector<int> adj[NMAX];
void add(int a, int b){
if(a % n == e[b][0]) adj[b + n].emplace_back(a);
else adj[b].emplace_back(a);
return;
}
void dfs(int x, int dist){
d[x] = dist;
for(int& nx : adj[x]){
if(d[nx] == -1) dfs(nx, dist + 1);
else if(nx == p) cy = dist + 1;
}
return;
}
/*
void answer(int x){
cout << x << '\n';
return;
}*/
void count_routes(int n_, int m_, int p_, int r_[][2], int q_, int g_[]){
n = n_; m = m_; p = p_; q = q_;
memset(e, -1, sizeof(e));
for(int i = 0; i < m; i++){
a = r_[i][0]; b = r_[i][1];
if(e[a][0] == -1) e[a][0] = b;
else if(e[a][1] == -1) e[a][1] = b;
if(e[b][0] == -1) e[b][0] = a;
else if(e[b][1] == -1) e[b][1] = a;
}
for(int i =0; i < n; i++)
if(e[i][1] == -1) e[i][1] = e[i][0];
for(int i = 0; i < n; i++)
if(e[i][0] != -1){
add(i, e[i][0]);
add(i + n, e[i][1]);
}
memset(d, -1, sizeof(d));
dfs(p, 0);
swap(d, dd); cy2 = cy; cy = 0;
memset(d, -1, sizeof(d));
p += n; dfs(p, 0);
for(int j = 0; j < q; j++){
int ans = 0;
a = g_[j];
for(int i = 0; i < n; i++){
if(d[i] == a || cy && a > d[i] && (a - d[i]) % cy == 0) ans++;
else if(dd[i] == a || cy2 && a > dd[i] && (a - dd[i]) % cy2 == 0) ans++;
}
answer(ans);
}
return;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> p;
for(int i = 0; i < m; i++) cin >> r[i][0] >> r[i][1];
cin >> q;
for(int i = 0; i < q; i++) cin >> g[i];
count_routes(n, m, p, r, q, g);
return 0;
}*/
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:60:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
60 | if(d[i] == a || cy && a > d[i] && (a - d[i]) % cy == 0) ans++;
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:61:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
61 | else if(dd[i] == a || cy2 && a > dd[i] && (a - dd[i]) % cy2 == 0) ans++;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
