#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "garden.h"
#include "gardenlib.h"
vector<int> adj1[N], adj2[N];
void count_routes(int n, int m, int p, int R[][2], int q, int a[])
{
rep(i,m){
int u = R[i][0], v = R[i][1];
adj1[u].pb(v), adj1[v].pb(u);
}
vector<int> nxt(n*2,-1);
rep(u,n){
auto edges = adj1[u];
if(sz(edges) >= 2){
{
int v = edges[1];
if(u == adj1[v][0]){
nxt[u*2] = v*2;
}
else{
nxt[u*2] = v*2+1;
}
}
{
int v = edges[0];
if(u == adj1[v][0]){
nxt[u*2+1] = v*2;
}
else{
nxt[u*2+1] = v*2+1;
}
}
}
else{
int v = edges[0];
if(u == adj1[v][0]){
nxt[u*2] = v*2;
}
else{
nxt[u*2] = v*2+1;
}
}
}
vector<int> indeg(2*n);
rep(i,2*n){
if(nxt[i] != -1){
indeg[nxt[i]]++;
}
}
queue<int> que;
rep(i,2*n){
if(!indeg[i]){
que.push(i);
}
}
while(!que.empty()){
int u = que.front();
que.pop();
if(nxt[u] != -1){
indeg[nxt[u]]--;
if(!indeg[nxt[u]]){
que.push(nxt[u]);
}
}
}
vector<int> cyc_siz(2);
for(int s = p*2; s <= p*2+1; ++s){
if(!indeg[s]) conts;
int u = nxt[s];
cyc_siz[s&1] = 1;
while(u != s){
cyc_siz[s&1]++;
u = nxt[u];
}
}
rep(u,2*n){
int v = nxt[u];
if(v == -1) conts;
adj2[v].pb(u);
}
int dis[2*n][2];
memset(dis,0x3f,sizeof dis);
rep(x,2){
que.push(p*2+x);
dis[p*2+x][x] = 0;
while(!que.empty()){
int u = que.front();
que.pop();
trav(v,adj2[u]){
if(dis[u][x]+1 >= dis[v][x]) conts;
que.push(v);
dis[v][x] = dis[u][x]+1;
}
}
}
vector<int> node_id(n);
rep(i,n){
node_id[i] = 2*i+1;
if(sz(adj1[i]) == 1){
node_id[i]--;
}
}
int modk[q][2];
memset(modk,-1,sizeof modk);
rep(i,q){
int k = a[i];
rep(j,2){
if(cyc_siz[j]){
modk[i][j] = k%cyc_siz[j];
}
}
}
int mod_dis[2*n][2];
memset(mod_dis,0x3f,sizeof mod_dis);
rep(i,2*n){
rep(j,2){
if(cyc_siz[j]){
mod_dis[i][j] = dis[i][j]%cyc_siz[j];
}
}
}
vector<pii> queries(q);
rep(i,q) queries[i] = {a[i],i};
sort(all(queries));
vector<pii> sorted_dis;
rep(i,n){
int u = node_id[i];
rep(x,2){
sorted_dis.pb({dis[u][x],mod_dis[u][x]});
}
}
sort(all(sorted_dis));
map<int,int> mp1,mp2;
for(auto [x,y] : sorted_dis){
mp1[x]++;
}
vector<int> ans(q);
int ptr = 0;
rep(i,q){
auto [k,id] = queries[i];
while(ptr < sz(sorted_dis) and sorted_dis[ptr].ff < k){
mp2[sorted_dis[ptr++].ss]++;
}
ans[id] = mp1[k];
rep(x,2){
ans[id] += mp2[modk[id][x]];
}
}
rep(i,q){
answer(ans[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
