#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 200001;
vector <vector <int> > g(nmax);
int nx[nmax];
int p[nmax];
vector <vector <int> > vv[2];
void bfs(int s, int ind, int n){
int cnt = 0;
queue <int> q;
q.push(s);
vector <bool> used(2 * n + 1);
used[s] = true;
fill(p, p + 2 * n, -1);
p[s] = -1;
int cyc = s;
bool rrr = false;
while(!q.empty()){
int v = q.front(); q.pop();
for(int to : g[v]){
if(used[to]){
cyc = v;rrr = true;
break;
}
else p[to] = v, q.push(to), used[to] = true;
}
if(rrr) break;
}
while(cyc != -1){
cnt++;
cyc = p[cyc];
}
vv[ind].resize(cnt);
while(!q.empty())q.pop();
used.assign(2 * n + 1, false);
vector <int> depth(2 * n + 1, -1);
depth[s] = 0;
q.push(s);
while(!q.empty()){
int v = q.front(); q.pop();
for(int to : g[v]){
if(depth[to] == -1) depth[to] = depth[v] + 1, q.push(to);
}
}
//cout << cnt;
for(int i = n; i < 2 * n; i++){
// cout << depth[i] << ' ';
if(depth[i] == -1) continue;
vv[ind][depth[i] % cnt].pb(depth[i]);
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int qv[]){
int f[n];
// cout << 1;
fill(f, f + n, -1);
fill(nx, nx + 2 * n, -1);
for(int i = 0; i < m; i++){
int u = r[i][0], v = r[i][1];
//cout << u << ' ' << v;
if(f[u] == -1 && f[v] == -1){
nx[u + n] = v;
nx[v + n] = u;
}
if(f[u] == -1 && f[v] == 1){
nx[u + n] = v + n;
if(nx[v] == -1) nx[v] = u;
}
if(f[v] == -1 && f[u] == 1){
nx[v + n] = u + n;
if(nx[u] == -1) nx[u] = v;
}
if(f[v] == 1 && f[u] == 1){
if(nx[u] == -1) nx[u] = v + n;
if(nx[v] == -1) nx[v] = u + n;
}
f[u] = f[v] = 1;
}
// cout << 1;
for(int i = 0; i < 2 * n; i++){
if(nx[i] == -1 && i < n){
nx[i] = nx[i + n];
}
// cout << nx[i] << ' ';
if(nx[i] != -1) g[nx[i]].pb(i);
}
bfs(p, 0, n);
bfs(p + n, 1, n);
for(int i = 0; i < q; i++){
int k = qv[i];
int l = vv[0].size();
int o = k % l;
int ans = 0;
ans += upper_bound(vv[0][o].begin(), vv[0][o].end(), k) - vv[0][o].begin();
if(l == 1) ans -= lower_bound(vv[0][o].begin(), vv[0][o].end(), k) - vv[0][o].begin();
l = vv[1].size();
o = k % l;
ans += upper_bound(vv[1][o].begin(), vv[1][o].end(), k) - vv[1][o].begin();
if(l == 1) ans -= lower_bound(vv[1][o].begin(), vv[1][o].end(), k) - vv[1][o].begin();
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
