#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>
#define ff first
#define ss second
#define PB push_back
#define sz(x) int(x.size())
#define rsz resize
#define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation
#define all(x) (x).begin(),(x).end()
#define eps 1e-9
// more abusive notation (use at your own risk):
// #define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
// debugging
void __print(int x) {std::cerr << x;}
void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */
void __print(unsigned x) {std::cerr << x;}
void __print(ull x) {std::cerr << x;}
void __print(float x) {std::cerr << x;}
void __print(double x) {std::cerr << x;}
void __print(ld x) {std::cerr << x;}
void __print(char x) {std::cerr << '\'' << x << '\'';}
void __print(const char *x) {std::cerr << '\"' << x << '\"';}
void __print(const string& x) {std::cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';}
template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";}
void _print() {std::cerr << "]\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);}
void println() {std::cerr << ">--------------------<" << endl;}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */
// const variables
constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7
void setIO(const string& str) {// fast input/output
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (str.empty()) return;
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
#include "garden.h"
#include "gardenlib.h"
struct DSU {
int N;
vi parent, siz;
vc<array<int, 2>> change;
DSU() {}
DSU(int n) {
N = n;
parent.clear(), siz.clear();
parent.rsz(N+1), siz.rsz(N+1, 1);
iota(1 + all(parent), 1);
}
int find_set(int v) {
if (parent[v] == v) return v;
else return parent[v] = find_set(parent[v]);
}
bool unite(int a, int b) {
a = find_set(a), b = find_set(b);
if (a == b) return false;
if (siz[a] < siz[b]) swap(a, b);
parent[b] = a;
siz[a] += siz[b];
change.PB({a, b});
return true;
}
void roll_back() {
array<int, 2> p = change.back();
change.pop_back();
parent[p[1]] = p[1];
siz[p[0]] -= siz[p[1]];
}
bool connected(int a, int b) {
return find_set(a) == find_set(b);
}
bool connected() {
return siz[find_set(1)] == N;
}
};
int N, M, P, Q, L, temp_p;
vc<vc<pii>> adj; // the adjacency list
vi f, beauty, vst, dp, deg;
// f: the element that i is adjacent to
// beauty: the maximum beauty of any edge including i
// dp: the distance from v to p
// deg: degree of the vertices
// 2 * i -> most beautiful
// 2 * i + 1 -> second most beautiful
vc<vi> adj_; // the adjacency list of the modified graph
vc<pii> queries; // answering queries offline
vi ans; // answer for each query
DSU d;
bool in_cycle = false; // whether p is in the cycle or not
void answer_2005() {
//debug(P);
//debug(in_cycle);
if (!in_cycle) { // then the portion of vertices that can reach P form a DAG
vi cnt(2 * N, 0); // cnt[i] = number of paths with dp[v] = i
for (int i = 0; i < N; ++i) {
if (dp[2 * i] == INF) continue;
cnt[dp[2 * i]]++;
}
for (int i = 0; i < Q; ++i) {
if (queries[i].ff <= 2 * N - 1) ans[queries[i].ss] += cnt[queries[i].ff];
// else ans[queries[i].ss] = 0 <---- old code, it doesn't make any sense because we have to add 0, not set it to 0
}
} else {
vi cnt(L, 0); // cnt[i] = number of paths with dp[v] === i mod L, L = length of the cycle
vi order(N);
iota(all(order), 0);
sort(all(order), [&](const int& a, const int& b) { // sort vertices in order of increasing distance
return dp[2 * a] < dp[2 * b];
});
int ptr = 0;
//debug(L);
for (int i = 0; i < Q; ++i) {
while (ptr < N && dp[2 * order[ptr]] <= queries[i].ff) { // while the distance is smaller than K
cnt[dp[2 * order[ptr]]%L]++;
ptr++;
}
//debug(cnt);
//debug(queries[i].ff % L);
ans[queries[i].ss] += cnt[queries[i].ff % L];
}
}
}
void construction() {
d = DSU(2 * N); // keep track of all connected components
adj_.rsz(2 * N), f.rsz(2 * N);
for (int i = 0; i < N; ++i) {
//debug(i);
set<pii> st;
fch(u, adj[i]) {
st.insert({u.ss, u.ff}); // sort the adjacent vertices in order
}
//debug(st);
// set values for f[i]
if (sz(st) == 1) {
int u = (*st.begin()).ss, w = (*st.begin()).ff;
f[2 * i] = f[2 * i + 1] = 2 * u + (w == beauty[u]); // when beauty[u] == -1, it will just equal to 2 * u
} else if (sz(st) >= 2) {
int u1 = (*st.begin()).ss, u2 = (*next(st.begin())).ss;
int w1 = (*st.begin()).ff, w2 = (*next(st.begin())).ff;
f[2 * i] = 2 * u1 + (w1 == beauty[u1]);
f[2 * i + 1] = 2 * u2 + (w2 == beauty[u2]);
}
}
for (int i = 0; i < 2 * N; ++i) {
adj_[f[i]].PB(i); // adj_: the reverse of f
d.unite(f[i], i); // update
//cerr << i << ' ' << f[i] << '\n';
}
}
void compute() {
in_cycle = false;
vst.clear(), vst.rsz(2 * N, 0), dp.clear(), dp.rsz(2 * N, INF);
for (int i = 0; i < 2 * N; ++i) {
if (!vst[d.find_set(i)]) { // checking if this component is visited
vst[d.find_set(i)] = 1;
int t = f[i]; // tortoise and hare
int h = f[f[i]];
while (t != h) {
t = f[t];
h = f[f[h]];
}
L = 1; // the length of the cycle that P is in
if (t == P) in_cycle = true;
t = f[t];
while (t != h) {
L++;
if (t == P) {
in_cycle = true; // DONT BREAK HERE
}
t = f[t];
}
if (in_cycle) {
break; // because P is in exactly one cycle and we have found it
}
}
}
vst.clear(), vst.rsz(2 * N, 0);
queue<int> q;
q.push(P);
dp[P] = 0;
vst[P] = 1;
while (!q.empty()) {
int v = q.front();
q.pop();
fch(u, adj_[v]) { // updating the shortest paths to each vertex
if (!vst[u]) {
vst[u] = 1;
dp[u] = dp[v] + 1;
q.push(u);
}
}
}
}
void count_routes(int n, int m, int p, int R[][2], int q, int g[]) {
N = n, M = m, P = p, Q = q;
adj.rsz(N), queries.rsz(Q), beauty.rsz(N, M), ans.rsz(Q), deg.rsz(N, 0);
for (int i = 0; i < M; ++i) {
int a = R[i][0], b = R[i][1];
// debug(i);
// debug(a, b);
assert(a < N && b < N);
ckmin(beauty[a], i);
ckmin(beauty[b], i);
adj[a].PB({b, i});
adj[b].PB({a, i});
deg[a]++, deg[b]++;
}
for (int i = 0; i < N; ++i) {
if (deg[i] == 1) {
beauty[i] = -1; // only a single edge going from this vertex
}
}
for (int i = 0; i < Q; ++i) {
queries[i] = {g[i], i};
}
sort(all(queries)); // sort the queries by their value g[i]
construction(); // construct the tree
temp_p = P;
P = 2 * P; // first, compute the answer assuming that all paths must end at 2 * P
compute();
answer_2005();
P = 2 * temp_p + 1; // assume that all paths end at 2 * P + 1
compute();
answer_2005();
for (int i = 0; i < Q; ++i) {
answer(ans[i]);
}
}
/*
int r[200000][2];
int g[200000];
signed main() { // TIME YOURSELF !!!
setIO("");
int n, m, p, q;
cin >> n >> m >> p;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
r[i][0] = a, r[i][1] = b;
//debug(r[i][0], r[i][1]);
}
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> g[i];
//debug(g[i]);
}
count_routes(n, m, p, r, q, g);
return 0;
}*/
// TLE -> TRY NOT USING DEFINE INT LONG LONG
// CE -> CHECK LINE 45
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler
Compilation message
garden.cpp: In function 'void setIO(const string&)':
garden.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen((str + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen((str + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
516 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
2 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
516 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
2 ms |
860 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
11 ms |
7636 KB |
Output is correct |
| 12 |
Correct |
25 ms |
11216 KB |
Output is correct |
| 13 |
Correct |
47 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
77 ms |
32448 KB |
Output is correct |
| 15 |
Correct |
95 ms |
33428 KB |
Output is correct |
| 16 |
Correct |
70 ms |
24176 KB |
Output is correct |
| 17 |
Correct |
56 ms |
21652 KB |
Output is correct |
| 18 |
Correct |
22 ms |
11432 KB |
Output is correct |
| 19 |
Correct |
94 ms |
33728 KB |
Output is correct |
| 20 |
Correct |
83 ms |
33472 KB |
Output is correct |
| 21 |
Correct |
63 ms |
24536 KB |
Output is correct |
| 22 |
Correct |
60 ms |
21568 KB |
Output is correct |
| 23 |
Correct |
79 ms |
35520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
516 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
2 ms |
860 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
11 ms |
7636 KB |
Output is correct |
| 12 |
Correct |
25 ms |
11216 KB |
Output is correct |
| 13 |
Correct |
47 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
77 ms |
32448 KB |
Output is correct |
| 15 |
Correct |
95 ms |
33428 KB |
Output is correct |
| 16 |
Correct |
70 ms |
24176 KB |
Output is correct |
| 17 |
Correct |
56 ms |
21652 KB |
Output is correct |
| 18 |
Correct |
22 ms |
11432 KB |
Output is correct |
| 19 |
Correct |
94 ms |
33728 KB |
Output is correct |
| 20 |
Correct |
83 ms |
33472 KB |
Output is correct |
| 21 |
Correct |
63 ms |
24536 KB |
Output is correct |
| 22 |
Correct |
60 ms |
21568 KB |
Output is correct |
| 23 |
Correct |
79 ms |
35520 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
10 ms |
7636 KB |
Output is correct |
| 26 |
Correct |
23 ms |
11216 KB |
Output is correct |
| 27 |
Correct |
47 ms |
24004 KB |
Output is correct |
| 28 |
Correct |
80 ms |
32704 KB |
Output is correct |
| 29 |
Correct |
88 ms |
34724 KB |
Output is correct |
| 30 |
Correct |
69 ms |
24288 KB |
Output is correct |
| 31 |
Correct |
60 ms |
21952 KB |
Output is correct |
| 32 |
Correct |
22 ms |
11472 KB |
Output is correct |
| 33 |
Correct |
78 ms |
33216 KB |
Output is correct |
| 34 |
Correct |
89 ms |
33724 KB |
Output is correct |
| 35 |
Correct |
83 ms |
24536 KB |
Output is correct |
| 36 |
Correct |
63 ms |
21704 KB |
Output is correct |
| 37 |
Correct |
77 ms |
35776 KB |
Output is correct |
| 38 |
Correct |
82 ms |
40084 KB |
Output is correct |
