#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define ll long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
/*
Algo: We have 2n nodes (i, 0/1 - is last node the largest)
Just for lmao
*/
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
const ll N = 3e5 + 5;
const ll oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
ll rnd(ll l, ll r){
ll temp = rng() % (r - l + 1);
return abs(temp) + l;
}
ll n, m, p, q;
vector<ll> Adj[N];
// cycles that node u can get
vector<ii> cyc[N][2];
//map<ii, ll> mp;
ii nxt[N][2];
ll mn_dist[N][2];
vector<ii> Adj2[N][2];
iiii savee[N];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N, m = M, p = P;
for(ll i = 0; i < m; i++){
Adj[R[i][0]].pb(R[i][1]);
Adj[R[i][1]].pb(R[i][0]);
//mp[{min(R[i][0], R[i][1]), m}
}
for(ll i = 0; i < n; i++){
// last trail is the best in all trails from i -> need to choose second if there is one
if(Adj[i].size() >= 2) nxt[i][1] = {Adj[i][1], (Adj[Adj[i][1]][0] == i)};
else nxt[i][1] = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
nxt[i][0] = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
}
for(ll i = 0; i < n; i++){
for(ll j = 0; j < 2; j++){
Adj2[nxt[i][j].fi][nxt[i][j].se].pb({i, j});
}
}
// finding the cycle for (p, 0)
ii itr = {p, 0};
ll len = 0;
while((!len || itr != make_pair(p, 0LL)) && len <= 2 * n){
len++;
itr = nxt[itr.fi][itr.se];
}
if(len > 2 * n) len = oo;
for(ll i = 0; i < n; i++) mn_dist[i][0] = mn_dist[i][1] = oo;
mn_dist[p][0] = 0;
queue<ii> bfs;
bfs.push({p, 0});
while(!bfs.empty()){
ii u = bfs.front();
bfs.pop();
for(auto it : Adj2[u.fi][u.se]){
if(mn_dist[it.fi][it.se] != oo) continue;
mn_dist[it.fi][it.se] = mn_dist[u.fi][u.se] + 1;
bfs.push(it);
}
}
for(ll i = 0; i < n; i++){
for(ll j = 0; j < 2; j++){
if(mn_dist[i][j] == oo) continue;
cyc[i][j].pb({mn_dist[i][j], len});
}
}
itr = {p, 1};
len = 0;
while((!len || itr != make_pair(p, 1LL)) && len <= 2 * n){
len++;
itr = nxt[itr.fi][itr.se];
}
if(len > 2 * n) len = oo;
for(ll i = 0; i < n; i++) mn_dist[i][0] = mn_dist[i][1] = oo;
mn_dist[p][1] = 0;
//queue<ii> bfs;
bfs.push({p, 1});
//cout << "OKAY\n";
while(!bfs.empty()){
ii u = bfs.front();
bfs.pop();
for(auto it : Adj2[u.fi][u.se]){
if(mn_dist[it.fi][it.se] != oo) continue;
mn_dist[it.fi][it.se] = mn_dist[u.fi][u.se] + 1;
bfs.push(it);
}
}
for(ll i = 0; i < n; i++){
for(ll j = 0; j < 2; j++){
if(mn_dist[i][j] == oo) continue;
cyc[i][j].pb({mn_dist[i][j], len});
//cout << i << " " << j << " " << mn_dist[i][j] << " " << len << "\n";
}
}
// exit(0);
for(ll i = 0; i < n; i++){
ii temp = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
savee[i] = {{-1, -1}, {-1, -1}};
for(auto it : cyc[temp.fi][temp.se]){
if(savee[i].fi.fi < 0) savee[i].fi = it;
else savee[i].se = it;
}
}
for(ll i = 0; i < Q; i++){
ll tol = 0;
G[i]--;
for(ll j = 0; j < n; j++){
//cout << temp.fi << " " << temp.se << "\n";
//cout << j << " " << Adj[j][0] << "\n";
//continue;
bool ck = 0;
if(savee[i].fi.fi >= 0){
ll diff = G[i] - savee[i].fi.fi;
ck = (diff >= 0 && !(diff % savee[i].fi.se));
if(!ck && savee[i].se.fi >= 0){
ll diff = G[i] - savee[i].se.fi;
ck = (diff >= 0 && !(diff % savee[i].se.se));
}
}
tol += ck;
}
//cout << i << " " << tol << "\n";
answer(tol);
//if(n >= 100000 && Q > 1) exit(0);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
35796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
35796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
35796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
