#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> ti;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
// whatever
const int SQ = 200;
const int MN = 100010;
vii go[MN];
vvi g;
int dp[MN];
bitset<MN> bs;
int sad(int u, vi& no) {
for(auto& it: no) {
bs.set(it);
}
for(int i=0;i<go[u].size();i++) {
int v = go[u][i].second;
if(!bs[v]) {
for(auto& it: no) {
bs.reset(it);
}
return go[u][i].first;
}
}
fill(begin(dp),end(dp),-1e9);
dp[u] = 0;
int res = -1;
for(int i=u;i>=0;i--) {
for(int j=0;j<g[i].size();j++) {
int v = g[i][j];
dp[v] = max(dp[v],dp[i]+1);
}
if(!bs[i]) {
res = max(res,dp[i]);
}
}
for(auto& it: no) {
bs.reset(it);
}
return res;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
g.assign(n,vi());
for(int i=0;i<m;i++) {
int a,b;
cin >> a >> b;
a--;b--;
g[b].push_back(a);
}
for(int i=0;i<n;i++) {
priority_queue<ti> bo;
for(int j=0;j<g[i].size();j++) {
int u = g[i][j];
bo.push({{go[u].front().first,0},u});
}
while(!bo.empty() && go[i].size() < SQ) {
ti ol = bo.top();bo.pop();
int u = ol.second;
ii co = ol.first;
int idx = co.second;
ii ens = go[u][idx];
ens.first++;
if(!bs[ens.second]) {
bs.set(ens.second);
go[i].push_back(ens);
}
while(idx < go[u].size() && bs[go[u][idx].second]) {
idx++;
}
if(idx < go[u].size()) {
bo.push({{go[u][idx].first,idx},u});
}
}
if(go[i].size() < SQ) {
go[i].push_back({0,i});
}
for(auto& it: go[i]) {
bs.reset(it.second);
}
}
for(int i=0;i<q;i++) {
int tr,lo;
cin >> tr >> lo;
vi no;
tr--;
for(int j=0;j<lo;j++) {
int t;
cin >> t;
t--;
no.push_back(t);
}
cout << sad(tr,no) << '\n';
}
}
Compilation message
bitaro.cpp: In function 'int sad(int, vi&)':
bitaro.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<go[u].size();i++) {
| ~^~~~~~~~~~~~~
bitaro.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j=0;j<g[i].size();j++) {
| ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int j=0;j<g[i].size();j++) {
| ~^~~~~~~~~~~~
bitaro.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while(idx < go[u].size() && bs[go[u][idx].second]) {
| ~~~~^~~~~~~~~~~~~~
bitaro.cpp:77:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(idx < go[u].size()) {
| ~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
3072 KB |
Output is correct |
3 |
Correct |
2 ms |
3072 KB |
Output is correct |
4 |
Correct |
2 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
5 ms |
3200 KB |
Output is correct |
8 |
Correct |
16 ms |
4608 KB |
Output is correct |
9 |
Correct |
14 ms |
4608 KB |
Output is correct |
10 |
Correct |
14 ms |
4992 KB |
Output is correct |
11 |
Correct |
13 ms |
4480 KB |
Output is correct |
12 |
Correct |
9 ms |
3840 KB |
Output is correct |
13 |
Correct |
13 ms |
4864 KB |
Output is correct |
14 |
Correct |
11 ms |
4224 KB |
Output is correct |
15 |
Correct |
7 ms |
3328 KB |
Output is correct |
16 |
Correct |
10 ms |
3840 KB |
Output is correct |
17 |
Correct |
11 ms |
3968 KB |
Output is correct |
18 |
Correct |
8 ms |
3584 KB |
Output is correct |
19 |
Correct |
12 ms |
4020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
3072 KB |
Output is correct |
3 |
Correct |
2 ms |
3072 KB |
Output is correct |
4 |
Correct |
2 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
5 ms |
3200 KB |
Output is correct |
8 |
Correct |
16 ms |
4608 KB |
Output is correct |
9 |
Correct |
14 ms |
4608 KB |
Output is correct |
10 |
Correct |
14 ms |
4992 KB |
Output is correct |
11 |
Correct |
13 ms |
4480 KB |
Output is correct |
12 |
Correct |
9 ms |
3840 KB |
Output is correct |
13 |
Correct |
13 ms |
4864 KB |
Output is correct |
14 |
Correct |
11 ms |
4224 KB |
Output is correct |
15 |
Correct |
7 ms |
3328 KB |
Output is correct |
16 |
Correct |
10 ms |
3840 KB |
Output is correct |
17 |
Correct |
11 ms |
3968 KB |
Output is correct |
18 |
Correct |
8 ms |
3584 KB |
Output is correct |
19 |
Correct |
12 ms |
4020 KB |
Output is correct |
20 |
Correct |
168 ms |
5880 KB |
Output is correct |
21 |
Correct |
125 ms |
7288 KB |
Output is correct |
22 |
Correct |
169 ms |
7672 KB |
Output is correct |
23 |
Correct |
106 ms |
7288 KB |
Output is correct |
24 |
Correct |
1064 ms |
153300 KB |
Output is correct |
25 |
Correct |
1081 ms |
157540 KB |
Output is correct |
26 |
Correct |
1085 ms |
158072 KB |
Output is correct |
27 |
Correct |
1255 ms |
212728 KB |
Output is correct |
28 |
Correct |
1248 ms |
213116 KB |
Output is correct |
29 |
Correct |
1278 ms |
213368 KB |
Output is correct |
30 |
Correct |
1274 ms |
212972 KB |
Output is correct |
31 |
Correct |
1271 ms |
207604 KB |
Output is correct |
32 |
Correct |
1282 ms |
213248 KB |
Output is correct |
33 |
Correct |
913 ms |
135032 KB |
Output is correct |
34 |
Correct |
788 ms |
116612 KB |
Output is correct |
35 |
Correct |
918 ms |
134080 KB |
Output is correct |
36 |
Correct |
1120 ms |
174264 KB |
Output is correct |
37 |
Correct |
1036 ms |
162056 KB |
Output is correct |
38 |
Correct |
1109 ms |
174840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
3072 KB |
Output is correct |
3 |
Correct |
2 ms |
3072 KB |
Output is correct |
4 |
Correct |
2 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
5 ms |
3200 KB |
Output is correct |
8 |
Correct |
16 ms |
4608 KB |
Output is correct |
9 |
Correct |
14 ms |
4608 KB |
Output is correct |
10 |
Correct |
14 ms |
4992 KB |
Output is correct |
11 |
Correct |
13 ms |
4480 KB |
Output is correct |
12 |
Correct |
9 ms |
3840 KB |
Output is correct |
13 |
Correct |
13 ms |
4864 KB |
Output is correct |
14 |
Correct |
11 ms |
4224 KB |
Output is correct |
15 |
Correct |
7 ms |
3328 KB |
Output is correct |
16 |
Correct |
10 ms |
3840 KB |
Output is correct |
17 |
Correct |
11 ms |
3968 KB |
Output is correct |
18 |
Correct |
8 ms |
3584 KB |
Output is correct |
19 |
Correct |
12 ms |
4020 KB |
Output is correct |
20 |
Correct |
168 ms |
5880 KB |
Output is correct |
21 |
Correct |
125 ms |
7288 KB |
Output is correct |
22 |
Correct |
169 ms |
7672 KB |
Output is correct |
23 |
Correct |
106 ms |
7288 KB |
Output is correct |
24 |
Correct |
1064 ms |
153300 KB |
Output is correct |
25 |
Correct |
1081 ms |
157540 KB |
Output is correct |
26 |
Correct |
1085 ms |
158072 KB |
Output is correct |
27 |
Correct |
1255 ms |
212728 KB |
Output is correct |
28 |
Correct |
1248 ms |
213116 KB |
Output is correct |
29 |
Correct |
1278 ms |
213368 KB |
Output is correct |
30 |
Correct |
1274 ms |
212972 KB |
Output is correct |
31 |
Correct |
1271 ms |
207604 KB |
Output is correct |
32 |
Correct |
1282 ms |
213248 KB |
Output is correct |
33 |
Correct |
913 ms |
135032 KB |
Output is correct |
34 |
Correct |
788 ms |
116612 KB |
Output is correct |
35 |
Correct |
918 ms |
134080 KB |
Output is correct |
36 |
Correct |
1120 ms |
174264 KB |
Output is correct |
37 |
Correct |
1036 ms |
162056 KB |
Output is correct |
38 |
Correct |
1109 ms |
174840 KB |
Output is correct |
39 |
Correct |
1130 ms |
155400 KB |
Output is correct |
40 |
Correct |
1100 ms |
155632 KB |
Output is correct |
41 |
Correct |
1089 ms |
156152 KB |
Output is correct |
42 |
Correct |
1093 ms |
156280 KB |
Output is correct |
43 |
Correct |
1090 ms |
155128 KB |
Output is correct |
44 |
Correct |
207 ms |
8696 KB |
Output is correct |
45 |
Correct |
184 ms |
7800 KB |
Output is correct |
46 |
Correct |
184 ms |
7928 KB |
Output is correct |
47 |
Correct |
170 ms |
7416 KB |
Output is correct |
48 |
Correct |
177 ms |
7292 KB |
Output is correct |
49 |
Correct |
1317 ms |
214396 KB |
Output is correct |
50 |
Correct |
1269 ms |
213128 KB |
Output is correct |
51 |
Correct |
172 ms |
8848 KB |
Output is correct |
52 |
Correct |
141 ms |
7928 KB |
Output is correct |
53 |
Correct |
1146 ms |
174712 KB |
Output is correct |
54 |
Correct |
1101 ms |
162552 KB |
Output is correct |
55 |
Correct |
1115 ms |
173440 KB |
Output is correct |
56 |
Correct |
1063 ms |
162552 KB |
Output is correct |
57 |
Correct |
209 ms |
8952 KB |
Output is correct |
58 |
Correct |
214 ms |
8952 KB |
Output is correct |
59 |
Correct |
177 ms |
7928 KB |
Output is correct |
60 |
Correct |
179 ms |
7928 KB |
Output is correct |
61 |
Correct |
1412 ms |
213368 KB |
Output is correct |
62 |
Correct |
1194 ms |
174584 KB |
Output is correct |
63 |
Correct |
1113 ms |
161688 KB |
Output is correct |
64 |
Correct |
1665 ms |
213388 KB |
Output is correct |
65 |
Correct |
1437 ms |
173980 KB |
Output is correct |
66 |
Correct |
1063 ms |
162808 KB |
Output is correct |
67 |
Correct |
1568 ms |
213348 KB |
Output is correct |
68 |
Correct |
1285 ms |
174584 KB |
Output is correct |
69 |
Correct |
1033 ms |
160248 KB |
Output is correct |
70 |
Correct |
1268 ms |
213512 KB |
Output is correct |
71 |
Correct |
1119 ms |
174712 KB |
Output is correct |
72 |
Correct |
1053 ms |
162296 KB |
Output is correct |
73 |
Correct |
1307 ms |
213368 KB |
Output is correct |
74 |
Correct |
1124 ms |
174460 KB |
Output is correct |
75 |
Correct |
1087 ms |
162296 KB |
Output is correct |
76 |
Correct |
1309 ms |
214396 KB |
Output is correct |
77 |
Correct |
1263 ms |
213368 KB |
Output is correct |
78 |
Correct |
1262 ms |
213220 KB |
Output is correct |
79 |
Correct |
165 ms |
8696 KB |
Output is correct |
80 |
Correct |
145 ms |
7800 KB |
Output is correct |
81 |
Correct |
131 ms |
7288 KB |
Output is correct |
82 |
Correct |
1326 ms |
214232 KB |
Output is correct |
83 |
Correct |
1333 ms |
208888 KB |
Output is correct |
84 |
Correct |
1263 ms |
213116 KB |
Output is correct |
85 |
Correct |
1269 ms |
207480 KB |
Output is correct |
86 |
Correct |
1256 ms |
213164 KB |
Output is correct |
87 |
Correct |
1276 ms |
208300 KB |
Output is correct |
88 |
Correct |
198 ms |
8576 KB |
Output is correct |
89 |
Correct |
209 ms |
8568 KB |
Output is correct |
90 |
Correct |
173 ms |
7672 KB |
Output is correct |
91 |
Correct |
179 ms |
7672 KB |
Output is correct |
92 |
Correct |
168 ms |
7324 KB |
Output is correct |
93 |
Correct |
177 ms |
7416 KB |
Output is correct |
94 |
Correct |
931 ms |
136188 KB |
Output is correct |
95 |
Correct |
840 ms |
116984 KB |
Output is correct |
96 |
Correct |
876 ms |
134520 KB |
Output is correct |
97 |
Correct |
800 ms |
117880 KB |
Output is correct |
98 |
Correct |
870 ms |
135220 KB |
Output is correct |
99 |
Correct |
783 ms |
117548 KB |
Output is correct |
100 |
Correct |
153 ms |
8696 KB |
Output is correct |
101 |
Correct |
142 ms |
8568 KB |
Output is correct |
102 |
Correct |
131 ms |
7672 KB |
Output is correct |
103 |
Correct |
114 ms |
7672 KB |
Output is correct |
104 |
Correct |
115 ms |
7320 KB |
Output is correct |
105 |
Correct |
109 ms |
7416 KB |
Output is correct |
106 |
Correct |
1137 ms |
174720 KB |
Output is correct |
107 |
Correct |
1095 ms |
163100 KB |
Output is correct |
108 |
Correct |
1093 ms |
174584 KB |
Output is correct |
109 |
Correct |
1041 ms |
161656 KB |
Output is correct |
110 |
Correct |
1096 ms |
174956 KB |
Output is correct |
111 |
Correct |
1058 ms |
162480 KB |
Output is correct |
112 |
Correct |
204 ms |
8696 KB |
Output is correct |
113 |
Correct |
212 ms |
8696 KB |
Output is correct |
114 |
Correct |
179 ms |
7800 KB |
Output is correct |
115 |
Correct |
177 ms |
7632 KB |
Output is correct |
116 |
Correct |
168 ms |
7288 KB |
Output is correct |
117 |
Correct |
175 ms |
7288 KB |
Output is correct |
118 |
Correct |
1277 ms |
213180 KB |
Output is correct |
119 |
Correct |
1101 ms |
174668 KB |
Output is correct |
120 |
Correct |
1049 ms |
161784 KB |
Output is correct |
121 |
Correct |
1280 ms |
212872 KB |
Output is correct |
122 |
Correct |
1094 ms |
174072 KB |
Output is correct |
123 |
Correct |
1047 ms |
161272 KB |
Output is correct |
124 |
Correct |
1261 ms |
213204 KB |
Output is correct |
125 |
Correct |
1088 ms |
174584 KB |
Output is correct |
126 |
Correct |
1032 ms |
161016 KB |
Output is correct |