This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define int long long
#include <bits/stdc++.h>
using namespace std;
namespace input {
const int N = 1 << 20;
char b[N], *p, *q;
char get() {
if (p == q) {
p = b;
q = b + fread(b, 1, N, stdin);
}
assert(p != q);
char c = *p;
p = next(p);
return c;
}
long read() {
char c = get();
long x = 0;
int t = 0;
while (c < '0' || c > '9') {
if (c == '-') {
t = 1;
}
c = get();
}
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = get();
}
return t < 1 ? x : x * (0 - 1);
}
};
using input::read;
const int V = (int) 6E5;
int n, m, x;
vector<pair<int, int>> e[V];
int t[V];
int p[V * 2];
int d[V * 2];
bitset<V * 2> f;
vector<int> a[V * 2];
int length[V * 2];
void generate() {
queue<int> q;
for (int i = 0; i < n * 2; i++) {
if (d[i] == 0) {
q.push(i);
}
}
while (q.empty() == 0) {
int u = q.front(), v = p[u];
q.pop();
f[u] = 1;
d[v] = d[v] - 1;
if (d[v] == 0) {
q.push(v);
}
}
for (int i = 0; i < n * 2; i++) {
if (f[i] == 0) {
vector<int> a;
for (int u = i; f[u] == 0; u = p[u]) {
a.push_back(u);
f[u] = 1;
}
for (auto u : a) {
length[u] = (int) a.size();
}
}
}
}
bitset<V * 2> state;
int dist[V * 2];
void DFS(int u) {
if (state[u] == 1) {
return;
}
state[u] = 1;
for (auto v : a[u]) {
if (state[v] == 0) {
dist[v] = dist[u] + 1;
DFS(v);
}
}
}
int count(int u, int k) {
for (int i = 0; i < n * 2; i++) {
state[i] = 0;
dist[i] = (int) 1E18;
}
dist[u] = 0;
DFS(u);
int sum = 0;
for (int i = 0; i < n; i++) {
if (length[u] == 0 && dist[i] == k) {
sum = sum + 1;
}
if (length[u] > 0 && k - dist[i] >= 0 && (k - dist[i]) % length[u] == 0) {
sum = sum + 1;
}
}
return sum;
}
void solve() {
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
// cin >> n >> m >> x;
n = N;
m = M;
x = P;
fill(t, t + n, m);
for (int i = 0; i < m; i++) {
int u, v;
// cin >> u >> v;
u = R[i][0];
v = R[i][1];
e[u].push_back({v, i});
e[v].push_back({u, i});
t[u] = min(t[u], i);
t[v] = min(t[v], i);
}
for (int u = 0; u < n; u++) {
int v, i;
tie(v, i) = e[u][0];
if (i != t[v]) {
p[u] = v;
d[v] = d[v] + 1;
a[v].push_back(u);
// cout << u << " " << v << "\n";
} else {
p[u] = v + n;
d[v + n] = d[v + n] + 1;
a[v + n].push_back(u);
// cout << u << " " << v + n << "\n";
}
if ((int) e[u].size() > 1) {
tie(v, i) = e[u][1];
}
if (i != t[v]) {
p[u + n] = v;
d[v] = d[v] + 1;
a[v].push_back(u + n);
// cout << u + n << " " << v << "\n";
} else {
p[u + n] = v + n;
d[v + n] = d[v + n] + 1;
a[v + n].push_back(u + n);
// cout << u + n << " " << v + n << "\n";
}
}
generate();
int q;
// cin >> q;
q = Q;
for (int i = 0; i < q; i++) {
int k;
// cin >> k;
k = G[i];
cout << count(x, k) + count(x + n, k) << " ";
}
}
// int32_t main() {
// ios::sync_with_stdio(0);
// cin.tie(nullptr);
// // double ST = clock();
// int t;
// t = 1;
// for (int i = 0; i < t; i++) {
// solve();
// }
// // double ED = clock();
// // cout << fixed << setprecision(10);
// // cout << (ED - ST) / CLOCKS_PER_SEC << "\n";
// return 0;
// }
Compilation message (stderr)
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long' and 'short' specified together
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long' and 'short' specified together
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long' and 'short' specified together
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long' and 'short' specified together
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long' and 'short' specified together
1 | #define int long long
| ^~~~
In file included from /usr/include/c++/10/cmath:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from garden.cpp:2:
/usr/include/c++/10/bits/cpp_type_traits.h:242:12: error: redefinition of 'struct std::__is_integer<long long int>'
242 | struct __is_integer<long long>
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/cpp_type_traits.h:214:12: note: previous definition of 'struct std::__is_integer<long long int>'
214 | struct __is_integer<int>
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/cpp_type_traits.h:249:12: error: redefinition of 'struct std::__is_integer<long long unsigned int>'
249 | struct __is_integer<unsigned long long>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/cpp_type_traits.h:221:12: note: previous definition of 'struct std::__is_integer<long long unsigned int>'
221 | struct __is_integer<unsigned int>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cmath:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from garden.cpp:2:
/usr/include/c++/10/ext/type_traits.h:95:12: error: redefinition of 'struct __gnu_cxx::__add_unsigned<long long int>'
95 | struct __add_unsigned<long long>
| ^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:87:12: note: previous definition of 'struct __gnu_cxx::__add_unsigned<long long int>'
87 | struct __add_unsigned<int>
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:138:12: error: redefinition of 'struct __gnu_cxx::__remove_unsigned<long long unsigned int>'
138 | struct __remove_unsigned<unsigned long long>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:130:12: note: previous definition of 'struct __gnu_cxx::__remove_unsigned<long long unsigned int>'
130 | struct __remove_unsigned<unsigned int>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cmath:45,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from garden.cpp:2:
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:13: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long
| ^~~~
garden.cpp:1:18: error: 'long long long' is too long for GCC
1 | #define int long long