#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]--;
}
}
rep(id,q){
int k = a[id];
int ans = 0;
rep(i,n){
int u = node_id[i];
bool ok = false;
rep(x,2){
int d = dis[u][x];
int cyc = cyc_siz[x];
if(cyc){
if(d <= k and (k-d)%cyc == 0){
ok = true;
}
}
else{
if(d == k){
ok = true;
}
}
}
ans += ok;
}
answer(ans);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
5 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
4 ms |
14940 KB |
Output is correct |
7 |
Correct |
4 ms |
14984 KB |
Output is correct |
8 |
Correct |
4 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
15196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
5 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
4 ms |
14940 KB |
Output is correct |
7 |
Correct |
4 ms |
14984 KB |
Output is correct |
8 |
Correct |
4 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
15196 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
12 ms |
17512 KB |
Output is correct |
12 |
Correct |
22 ms |
19292 KB |
Output is correct |
13 |
Correct |
37 ms |
28588 KB |
Output is correct |
14 |
Correct |
68 ms |
31568 KB |
Output is correct |
15 |
Correct |
84 ms |
31864 KB |
Output is correct |
16 |
Correct |
61 ms |
27540 KB |
Output is correct |
17 |
Correct |
56 ms |
26448 KB |
Output is correct |
18 |
Correct |
22 ms |
19284 KB |
Output is correct |
19 |
Correct |
71 ms |
31568 KB |
Output is correct |
20 |
Correct |
88 ms |
31812 KB |
Output is correct |
21 |
Correct |
62 ms |
27632 KB |
Output is correct |
22 |
Correct |
56 ms |
26272 KB |
Output is correct |
23 |
Correct |
75 ms |
32832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
5 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
4 ms |
14940 KB |
Output is correct |
7 |
Correct |
4 ms |
14984 KB |
Output is correct |
8 |
Correct |
4 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
15196 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
12 ms |
17512 KB |
Output is correct |
12 |
Correct |
22 ms |
19292 KB |
Output is correct |
13 |
Correct |
37 ms |
28588 KB |
Output is correct |
14 |
Correct |
68 ms |
31568 KB |
Output is correct |
15 |
Correct |
84 ms |
31864 KB |
Output is correct |
16 |
Correct |
61 ms |
27540 KB |
Output is correct |
17 |
Correct |
56 ms |
26448 KB |
Output is correct |
18 |
Correct |
22 ms |
19284 KB |
Output is correct |
19 |
Correct |
71 ms |
31568 KB |
Output is correct |
20 |
Correct |
88 ms |
31812 KB |
Output is correct |
21 |
Correct |
62 ms |
27632 KB |
Output is correct |
22 |
Correct |
56 ms |
26272 KB |
Output is correct |
23 |
Correct |
75 ms |
32832 KB |
Output is correct |
24 |
Correct |
4 ms |
14936 KB |
Output is correct |
25 |
Correct |
96 ms |
17500 KB |
Output is correct |
26 |
Correct |
132 ms |
19432 KB |
Output is correct |
27 |
Correct |
2037 ms |
29024 KB |
Output is correct |
28 |
Correct |
873 ms |
32340 KB |
Output is correct |
29 |
Correct |
2208 ms |
32636 KB |
Output is correct |
30 |
Correct |
1288 ms |
28288 KB |
Output is correct |
31 |
Correct |
1262 ms |
27008 KB |
Output is correct |
32 |
Correct |
112 ms |
19548 KB |
Output is correct |
33 |
Correct |
879 ms |
32472 KB |
Output is correct |
34 |
Correct |
2200 ms |
32620 KB |
Output is correct |
35 |
Correct |
1384 ms |
28500 KB |
Output is correct |
36 |
Correct |
1262 ms |
26988 KB |
Output is correct |
37 |
Correct |
715 ms |
33776 KB |
Output is correct |
38 |
Correct |
1788 ms |
38364 KB |
Output is correct |