#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#if 0
const int MOD = ;
inline int lgput(int a, int b) {
int ans = 1;
while(b > 0) {
if(b & 1) ans = (1LL * ans * a) % MOD;
b >>= 1;
a = (1LL * a * a) % MOD;
}
return ans;
}
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}
inline int inv(int x) {
return lgput(x, MOD - 2);
}
#endif
#if 0
int fact[], invfact[];
inline void prec(int n) {
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
invfact[n] = lgput(fact[n], MOD - 2);
for(int i = n - 1; i >= 0; i--) {
invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
}
}
inline int comb(int n, int k) {
if(n < k) return 0;
return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}
#endif
using namespace std;
const int MAXN = (int) 1e5;
const int BUCK = 200;
vector <int> g[MAXN + 1];
pair <int, int> nodes[MAXN + 1][BUCK];
int sz[MAXN + 1];
int dp[MAXN + 1];
bool vis[MAXN + 1];
int main() {
#if 0
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int i, n, m, q;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
}
for(i = 1; i <= n; i++) {
nodes[i][0] = {0, i};
sz[i] = 1;
}
auto combine = [&](int a, int b) -> void {
vector < pair <int, int> > aux;
int i = 0, j = 0;
while(i < sz[a] && j < sz[b]) {
if(nodes[a][i].first > nodes[b][j].first + 1) {
if(vis[nodes[a][i].second] == 0) {
aux.push_back(nodes[a][i]);
}
vis[nodes[a][i].second] = 1;
i++;
}
else {
nodes[b][j].first++;
if(vis[nodes[b][j].second] == 0) {
aux.push_back(nodes[b][j]);
}
vis[nodes[b][j].second] = 1;
nodes[b][j].first--;
j++;
}
}
while(i < sz[a]) {
if(vis[nodes[a][i].second] == 0) {
aux.push_back(nodes[a][i]);
}
vis[nodes[a][i].second] = 1;
i++;
}
while(j < sz[b]) {
nodes[b][j].first++;
if(vis[nodes[b][j].second] == 0) {
aux.push_back(nodes[b][j]);
}
vis[nodes[b][j].second] = 1;
nodes[b][j].first--;
j++;
}
for(auto it : aux) {
vis[it.second] = 0;
}
sz[a] = 0;
for(i = 0; i < aux.size() && i < BUCK; i++) {
nodes[a][sz[a]++] = aux[i];
}
};
for(i = 1; i <= n; i++) {
for(auto it : g[i]) {
combine(it, i);
}
}
while(q--) {
int nod, num;
cin >> nod >> num;
vector <int> cur(num);
for(i = 0; i < num; i++) {
cin >> cur[i];
vis[cur[i]] = 1;
}
int ans = -1;
if(cur.size() < BUCK) {
for(i = 0; i < sz[nod]; i++) {
if(vis[nodes[nod][i].second] == 0) {
ans = nodes[nod][i].first;
break;
}
}
}
else {
for(i = 1; i <= n; i++) {
dp[i] = -1;
}
for(i = 1; i <= nod; i++) {
if(vis[i] == 0) {
dp[i] = max(dp[i], 0);
}
if(dp[i] > -1) {
for(auto it : g[i]) {
dp[it] = max(dp[it], dp[i] + 1);
}
}
}
ans = dp[nod];
}
cout << ans << "\n";
for(auto it : cur) {
vis[it] = 0;
}
}
return 0;
}
Compilation message
bitaro.cpp: In lambda function:
bitaro.cpp:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < aux.size() && i < BUCK; i++) {
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2680 KB |
Output is correct |
3 |
Correct |
5 ms |
2680 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
8 ms |
4344 KB |
Output is correct |
6 |
Correct |
9 ms |
4344 KB |
Output is correct |
7 |
Correct |
8 ms |
4344 KB |
Output is correct |
8 |
Correct |
14 ms |
4344 KB |
Output is correct |
9 |
Correct |
14 ms |
4344 KB |
Output is correct |
10 |
Correct |
14 ms |
4344 KB |
Output is correct |
11 |
Correct |
14 ms |
4472 KB |
Output is correct |
12 |
Correct |
10 ms |
4344 KB |
Output is correct |
13 |
Correct |
14 ms |
4344 KB |
Output is correct |
14 |
Correct |
12 ms |
4344 KB |
Output is correct |
15 |
Correct |
10 ms |
4344 KB |
Output is correct |
16 |
Correct |
12 ms |
4344 KB |
Output is correct |
17 |
Correct |
12 ms |
4344 KB |
Output is correct |
18 |
Correct |
10 ms |
4344 KB |
Output is correct |
19 |
Correct |
12 ms |
4344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2680 KB |
Output is correct |
3 |
Correct |
5 ms |
2680 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
8 ms |
4344 KB |
Output is correct |
6 |
Correct |
9 ms |
4344 KB |
Output is correct |
7 |
Correct |
8 ms |
4344 KB |
Output is correct |
8 |
Correct |
14 ms |
4344 KB |
Output is correct |
9 |
Correct |
14 ms |
4344 KB |
Output is correct |
10 |
Correct |
14 ms |
4344 KB |
Output is correct |
11 |
Correct |
14 ms |
4472 KB |
Output is correct |
12 |
Correct |
10 ms |
4344 KB |
Output is correct |
13 |
Correct |
14 ms |
4344 KB |
Output is correct |
14 |
Correct |
12 ms |
4344 KB |
Output is correct |
15 |
Correct |
10 ms |
4344 KB |
Output is correct |
16 |
Correct |
12 ms |
4344 KB |
Output is correct |
17 |
Correct |
12 ms |
4344 KB |
Output is correct |
18 |
Correct |
10 ms |
4344 KB |
Output is correct |
19 |
Correct |
12 ms |
4344 KB |
Output is correct |
20 |
Correct |
827 ms |
7144 KB |
Output is correct |
21 |
Correct |
825 ms |
7064 KB |
Output is correct |
22 |
Correct |
829 ms |
7004 KB |
Output is correct |
23 |
Correct |
920 ms |
7092 KB |
Output is correct |
24 |
Correct |
1155 ms |
165248 KB |
Output is correct |
25 |
Correct |
1123 ms |
165256 KB |
Output is correct |
26 |
Correct |
1114 ms |
165232 KB |
Output is correct |
27 |
Correct |
1333 ms |
166384 KB |
Output is correct |
28 |
Correct |
1338 ms |
166240 KB |
Output is correct |
29 |
Correct |
1344 ms |
166260 KB |
Output is correct |
30 |
Correct |
1325 ms |
165580 KB |
Output is correct |
31 |
Correct |
1321 ms |
165564 KB |
Output is correct |
32 |
Correct |
1321 ms |
165636 KB |
Output is correct |
33 |
Correct |
948 ms |
166292 KB |
Output is correct |
34 |
Correct |
904 ms |
166288 KB |
Output is correct |
35 |
Correct |
951 ms |
166236 KB |
Output is correct |
36 |
Correct |
1164 ms |
166260 KB |
Output is correct |
37 |
Correct |
1142 ms |
166264 KB |
Output is correct |
38 |
Correct |
1163 ms |
166264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2680 KB |
Output is correct |
3 |
Correct |
5 ms |
2680 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
8 ms |
4344 KB |
Output is correct |
6 |
Correct |
9 ms |
4344 KB |
Output is correct |
7 |
Correct |
8 ms |
4344 KB |
Output is correct |
8 |
Correct |
14 ms |
4344 KB |
Output is correct |
9 |
Correct |
14 ms |
4344 KB |
Output is correct |
10 |
Correct |
14 ms |
4344 KB |
Output is correct |
11 |
Correct |
14 ms |
4472 KB |
Output is correct |
12 |
Correct |
10 ms |
4344 KB |
Output is correct |
13 |
Correct |
14 ms |
4344 KB |
Output is correct |
14 |
Correct |
12 ms |
4344 KB |
Output is correct |
15 |
Correct |
10 ms |
4344 KB |
Output is correct |
16 |
Correct |
12 ms |
4344 KB |
Output is correct |
17 |
Correct |
12 ms |
4344 KB |
Output is correct |
18 |
Correct |
10 ms |
4344 KB |
Output is correct |
19 |
Correct |
12 ms |
4344 KB |
Output is correct |
20 |
Correct |
827 ms |
7144 KB |
Output is correct |
21 |
Correct |
825 ms |
7064 KB |
Output is correct |
22 |
Correct |
829 ms |
7004 KB |
Output is correct |
23 |
Correct |
920 ms |
7092 KB |
Output is correct |
24 |
Correct |
1155 ms |
165248 KB |
Output is correct |
25 |
Correct |
1123 ms |
165256 KB |
Output is correct |
26 |
Correct |
1114 ms |
165232 KB |
Output is correct |
27 |
Correct |
1333 ms |
166384 KB |
Output is correct |
28 |
Correct |
1338 ms |
166240 KB |
Output is correct |
29 |
Correct |
1344 ms |
166260 KB |
Output is correct |
30 |
Correct |
1325 ms |
165580 KB |
Output is correct |
31 |
Correct |
1321 ms |
165564 KB |
Output is correct |
32 |
Correct |
1321 ms |
165636 KB |
Output is correct |
33 |
Correct |
948 ms |
166292 KB |
Output is correct |
34 |
Correct |
904 ms |
166288 KB |
Output is correct |
35 |
Correct |
951 ms |
166236 KB |
Output is correct |
36 |
Correct |
1164 ms |
166260 KB |
Output is correct |
37 |
Correct |
1142 ms |
166264 KB |
Output is correct |
38 |
Correct |
1163 ms |
166264 KB |
Output is correct |
39 |
Correct |
1175 ms |
166060 KB |
Output is correct |
40 |
Correct |
1153 ms |
165192 KB |
Output is correct |
41 |
Correct |
1121 ms |
164976 KB |
Output is correct |
42 |
Correct |
1301 ms |
165420 KB |
Output is correct |
43 |
Correct |
1138 ms |
165360 KB |
Output is correct |
44 |
Correct |
875 ms |
8300 KB |
Output is correct |
45 |
Correct |
841 ms |
7508 KB |
Output is correct |
46 |
Correct |
846 ms |
7544 KB |
Output is correct |
47 |
Correct |
877 ms |
7160 KB |
Output is correct |
48 |
Correct |
832 ms |
7020 KB |
Output is correct |
49 |
Correct |
1479 ms |
166928 KB |
Output is correct |
50 |
Correct |
1383 ms |
165780 KB |
Output is correct |
51 |
Correct |
859 ms |
8312 KB |
Output is correct |
52 |
Correct |
834 ms |
7416 KB |
Output is correct |
53 |
Correct |
1197 ms |
166776 KB |
Output is correct |
54 |
Correct |
1172 ms |
166648 KB |
Output is correct |
55 |
Correct |
1272 ms |
165772 KB |
Output is correct |
56 |
Correct |
1143 ms |
165804 KB |
Output is correct |
57 |
Correct |
862 ms |
8180 KB |
Output is correct |
58 |
Correct |
861 ms |
8164 KB |
Output is correct |
59 |
Correct |
839 ms |
7280 KB |
Output is correct |
60 |
Correct |
830 ms |
7292 KB |
Output is correct |
61 |
Correct |
1476 ms |
166136 KB |
Output is correct |
62 |
Correct |
1305 ms |
166252 KB |
Output is correct |
63 |
Correct |
1239 ms |
166136 KB |
Output is correct |
64 |
Correct |
1807 ms |
166268 KB |
Output is correct |
65 |
Correct |
1599 ms |
166264 KB |
Output is correct |
66 |
Correct |
1607 ms |
166296 KB |
Output is correct |
67 |
Correct |
1751 ms |
166264 KB |
Output is correct |
68 |
Correct |
1578 ms |
166220 KB |
Output is correct |
69 |
Correct |
1563 ms |
166264 KB |
Output is correct |
70 |
Correct |
1422 ms |
166252 KB |
Output is correct |
71 |
Correct |
1269 ms |
166272 KB |
Output is correct |
72 |
Correct |
1203 ms |
166500 KB |
Output is correct |
73 |
Correct |
1392 ms |
166392 KB |
Output is correct |
74 |
Correct |
1212 ms |
166264 KB |
Output is correct |
75 |
Correct |
1205 ms |
166356 KB |
Output is correct |
76 |
Correct |
1412 ms |
167420 KB |
Output is correct |
77 |
Correct |
1446 ms |
166480 KB |
Output is correct |
78 |
Correct |
1414 ms |
166416 KB |
Output is correct |
79 |
Correct |
861 ms |
8440 KB |
Output is correct |
80 |
Correct |
871 ms |
7416 KB |
Output is correct |
81 |
Correct |
830 ms |
7024 KB |
Output is correct |
82 |
Correct |
1393 ms |
166608 KB |
Output is correct |
83 |
Correct |
1440 ms |
166460 KB |
Output is correct |
84 |
Correct |
1401 ms |
165932 KB |
Output is correct |
85 |
Correct |
1368 ms |
165684 KB |
Output is correct |
86 |
Correct |
1340 ms |
165856 KB |
Output is correct |
87 |
Correct |
1362 ms |
165752 KB |
Output is correct |
88 |
Correct |
863 ms |
8312 KB |
Output is correct |
89 |
Correct |
852 ms |
8316 KB |
Output is correct |
90 |
Correct |
851 ms |
7416 KB |
Output is correct |
91 |
Correct |
845 ms |
7416 KB |
Output is correct |
92 |
Correct |
835 ms |
7032 KB |
Output is correct |
93 |
Correct |
828 ms |
7032 KB |
Output is correct |
94 |
Correct |
995 ms |
167032 KB |
Output is correct |
95 |
Correct |
986 ms |
167068 KB |
Output is correct |
96 |
Correct |
996 ms |
166268 KB |
Output is correct |
97 |
Correct |
963 ms |
166200 KB |
Output is correct |
98 |
Correct |
1027 ms |
166448 KB |
Output is correct |
99 |
Correct |
924 ms |
166328 KB |
Output is correct |
100 |
Correct |
953 ms |
8364 KB |
Output is correct |
101 |
Correct |
955 ms |
8384 KB |
Output is correct |
102 |
Correct |
925 ms |
7544 KB |
Output is correct |
103 |
Correct |
927 ms |
7388 KB |
Output is correct |
104 |
Correct |
913 ms |
7096 KB |
Output is correct |
105 |
Correct |
916 ms |
7032 KB |
Output is correct |
106 |
Correct |
1210 ms |
167268 KB |
Output is correct |
107 |
Correct |
1166 ms |
167044 KB |
Output is correct |
108 |
Correct |
1329 ms |
166388 KB |
Output is correct |
109 |
Correct |
1177 ms |
166384 KB |
Output is correct |
110 |
Correct |
1185 ms |
166388 KB |
Output is correct |
111 |
Correct |
1181 ms |
166508 KB |
Output is correct |
112 |
Correct |
888 ms |
8316 KB |
Output is correct |
113 |
Correct |
866 ms |
8540 KB |
Output is correct |
114 |
Correct |
846 ms |
7484 KB |
Output is correct |
115 |
Correct |
850 ms |
7396 KB |
Output is correct |
116 |
Correct |
836 ms |
7068 KB |
Output is correct |
117 |
Correct |
840 ms |
7020 KB |
Output is correct |
118 |
Correct |
1345 ms |
165724 KB |
Output is correct |
119 |
Correct |
1171 ms |
165748 KB |
Output is correct |
120 |
Correct |
1159 ms |
165868 KB |
Output is correct |
121 |
Correct |
1366 ms |
165940 KB |
Output is correct |
122 |
Correct |
1229 ms |
165752 KB |
Output is correct |
123 |
Correct |
1139 ms |
165712 KB |
Output is correct |
124 |
Correct |
1346 ms |
165608 KB |
Output is correct |
125 |
Correct |
1165 ms |
165752 KB |
Output is correct |
126 |
Correct |
1130 ms |
165772 KB |
Output is correct |