#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 350;
int n,m,k;
vector<int> adj[N],rev[N];
int id[N],dp[N];
queue<int> q;
vector<pair<int,int> > res[N];
bool out[N];
stack<int> st;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for(int i = 0;i < m;i++)
{
int a,b;
cin >> a >> b;
adj[a].push_back(b);
rev[b].push_back(a);
}
for(int u = 1;u <= n;u++)
{
for(int v : rev[u]) id[v] = 0;
for(int j = 0;j < K;j++)
{
pair<int,int> mx = {u,0};
for(int v : rev[u])
{
while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
}
res[u].push_back(mx);
out[mx.first] = true;
st.push(mx.first);
if(mx.first==u) break;
else id[mx.first]++;
}
while(!st.empty()) out[st.top()] = false,st.pop();
}
while(k--)
{
int u,am,mm;
cin >> u >> am,mm = am;
while(am--){ int x; cin >> x; out[x] = true; st.push(x); }
if(mm>=K)
{
for(int i = 1;i <= n;i++) dp[i] = INT_MIN;
dp[u] = 0;
int ans = -1;
if(!out[u]) ans = 0;
for(int i = u-1;i >= 1;i--)
{
for(int v : adj[i]) dp[i] = max(dp[i],dp[v]+1);
if(!out[i]) ans = max(ans,dp[i]);
}
cout << ans << '\n';
}
else
{
int ans = -1;
for(auto [x,y] : res[u]) if(!out[x]){ ans = y; break; }
cout << ans << '\n';
}
while(!st.empty()) out[st.top()] = false,st.pop();
}
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
| ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
| ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:67:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for(auto [x,y] : res[u]) if(!out[x]){ ans = y; break; }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7424 KB |
Output is correct |
2 |
Correct |
5 ms |
7424 KB |
Output is correct |
3 |
Correct |
5 ms |
7552 KB |
Output is correct |
4 |
Correct |
5 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
8 ms |
7936 KB |
Output is correct |
7 |
Correct |
9 ms |
7936 KB |
Output is correct |
8 |
Correct |
18 ms |
10752 KB |
Output is correct |
9 |
Correct |
18 ms |
10752 KB |
Output is correct |
10 |
Correct |
17 ms |
10752 KB |
Output is correct |
11 |
Correct |
16 ms |
10368 KB |
Output is correct |
12 |
Correct |
11 ms |
8704 KB |
Output is correct |
13 |
Correct |
16 ms |
10240 KB |
Output is correct |
14 |
Correct |
14 ms |
9444 KB |
Output is correct |
15 |
Correct |
10 ms |
8448 KB |
Output is correct |
16 |
Correct |
14 ms |
9344 KB |
Output is correct |
17 |
Correct |
14 ms |
9600 KB |
Output is correct |
18 |
Correct |
11 ms |
8576 KB |
Output is correct |
19 |
Correct |
15 ms |
9600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7424 KB |
Output is correct |
2 |
Correct |
5 ms |
7424 KB |
Output is correct |
3 |
Correct |
5 ms |
7552 KB |
Output is correct |
4 |
Correct |
5 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
8 ms |
7936 KB |
Output is correct |
7 |
Correct |
9 ms |
7936 KB |
Output is correct |
8 |
Correct |
18 ms |
10752 KB |
Output is correct |
9 |
Correct |
18 ms |
10752 KB |
Output is correct |
10 |
Correct |
17 ms |
10752 KB |
Output is correct |
11 |
Correct |
16 ms |
10368 KB |
Output is correct |
12 |
Correct |
11 ms |
8704 KB |
Output is correct |
13 |
Correct |
16 ms |
10240 KB |
Output is correct |
14 |
Correct |
14 ms |
9444 KB |
Output is correct |
15 |
Correct |
10 ms |
8448 KB |
Output is correct |
16 |
Correct |
14 ms |
9344 KB |
Output is correct |
17 |
Correct |
14 ms |
9600 KB |
Output is correct |
18 |
Correct |
11 ms |
8576 KB |
Output is correct |
19 |
Correct |
15 ms |
9600 KB |
Output is correct |
20 |
Correct |
509 ms |
13192 KB |
Output is correct |
21 |
Correct |
522 ms |
13048 KB |
Output is correct |
22 |
Correct |
506 ms |
13048 KB |
Output is correct |
23 |
Correct |
561 ms |
13116 KB |
Output is correct |
24 |
Correct |
1239 ms |
256376 KB |
Output is correct |
25 |
Correct |
1293 ms |
267896 KB |
Output is correct |
26 |
Correct |
1275 ms |
267004 KB |
Output is correct |
27 |
Correct |
1604 ms |
416764 KB |
Output is correct |
28 |
Correct |
1598 ms |
416888 KB |
Output is correct |
29 |
Correct |
1592 ms |
416940 KB |
Output is correct |
30 |
Correct |
1608 ms |
415736 KB |
Output is correct |
31 |
Correct |
1622 ms |
401036 KB |
Output is correct |
32 |
Correct |
1615 ms |
415736 KB |
Output is correct |
33 |
Correct |
1098 ms |
258588 KB |
Output is correct |
34 |
Correct |
935 ms |
212472 KB |
Output is correct |
35 |
Correct |
1085 ms |
256888 KB |
Output is correct |
36 |
Correct |
1355 ms |
337424 KB |
Output is correct |
37 |
Correct |
1304 ms |
305692 KB |
Output is correct |
38 |
Correct |
1358 ms |
338464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7424 KB |
Output is correct |
2 |
Correct |
5 ms |
7424 KB |
Output is correct |
3 |
Correct |
5 ms |
7552 KB |
Output is correct |
4 |
Correct |
5 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
8 ms |
7936 KB |
Output is correct |
7 |
Correct |
9 ms |
7936 KB |
Output is correct |
8 |
Correct |
18 ms |
10752 KB |
Output is correct |
9 |
Correct |
18 ms |
10752 KB |
Output is correct |
10 |
Correct |
17 ms |
10752 KB |
Output is correct |
11 |
Correct |
16 ms |
10368 KB |
Output is correct |
12 |
Correct |
11 ms |
8704 KB |
Output is correct |
13 |
Correct |
16 ms |
10240 KB |
Output is correct |
14 |
Correct |
14 ms |
9444 KB |
Output is correct |
15 |
Correct |
10 ms |
8448 KB |
Output is correct |
16 |
Correct |
14 ms |
9344 KB |
Output is correct |
17 |
Correct |
14 ms |
9600 KB |
Output is correct |
18 |
Correct |
11 ms |
8576 KB |
Output is correct |
19 |
Correct |
15 ms |
9600 KB |
Output is correct |
20 |
Correct |
509 ms |
13192 KB |
Output is correct |
21 |
Correct |
522 ms |
13048 KB |
Output is correct |
22 |
Correct |
506 ms |
13048 KB |
Output is correct |
23 |
Correct |
561 ms |
13116 KB |
Output is correct |
24 |
Correct |
1239 ms |
256376 KB |
Output is correct |
25 |
Correct |
1293 ms |
267896 KB |
Output is correct |
26 |
Correct |
1275 ms |
267004 KB |
Output is correct |
27 |
Correct |
1604 ms |
416764 KB |
Output is correct |
28 |
Correct |
1598 ms |
416888 KB |
Output is correct |
29 |
Correct |
1592 ms |
416940 KB |
Output is correct |
30 |
Correct |
1608 ms |
415736 KB |
Output is correct |
31 |
Correct |
1622 ms |
401036 KB |
Output is correct |
32 |
Correct |
1615 ms |
415736 KB |
Output is correct |
33 |
Correct |
1098 ms |
258588 KB |
Output is correct |
34 |
Correct |
935 ms |
212472 KB |
Output is correct |
35 |
Correct |
1085 ms |
256888 KB |
Output is correct |
36 |
Correct |
1355 ms |
337424 KB |
Output is correct |
37 |
Correct |
1304 ms |
305692 KB |
Output is correct |
38 |
Correct |
1358 ms |
338464 KB |
Output is correct |
39 |
Correct |
1314 ms |
259704 KB |
Output is correct |
40 |
Correct |
1263 ms |
261880 KB |
Output is correct |
41 |
Correct |
1267 ms |
264832 KB |
Output is correct |
42 |
Correct |
1447 ms |
262784 KB |
Output is correct |
43 |
Correct |
1288 ms |
262288 KB |
Output is correct |
44 |
Correct |
542 ms |
13432 KB |
Output is correct |
45 |
Correct |
517 ms |
13048 KB |
Output is correct |
46 |
Correct |
540 ms |
13092 KB |
Output is correct |
47 |
Correct |
530 ms |
13204 KB |
Output is correct |
48 |
Correct |
521 ms |
13048 KB |
Output is correct |
49 |
Correct |
1653 ms |
416880 KB |
Output is correct |
50 |
Correct |
1594 ms |
416504 KB |
Output is correct |
51 |
Correct |
540 ms |
13432 KB |
Output is correct |
52 |
Correct |
514 ms |
13048 KB |
Output is correct |
53 |
Correct |
1408 ms |
336120 KB |
Output is correct |
54 |
Correct |
1356 ms |
305912 KB |
Output is correct |
55 |
Correct |
1358 ms |
336120 KB |
Output is correct |
56 |
Correct |
1313 ms |
306424 KB |
Output is correct |
57 |
Correct |
545 ms |
13560 KB |
Output is correct |
58 |
Correct |
532 ms |
13560 KB |
Output is correct |
59 |
Correct |
505 ms |
13048 KB |
Output is correct |
60 |
Correct |
523 ms |
13040 KB |
Output is correct |
61 |
Correct |
1775 ms |
416504 KB |
Output is correct |
62 |
Correct |
1498 ms |
338944 KB |
Output is correct |
63 |
Correct |
1466 ms |
306168 KB |
Output is correct |
64 |
Correct |
1680 ms |
417656 KB |
Output is correct |
65 |
Correct |
1424 ms |
337272 KB |
Output is correct |
66 |
Correct |
1394 ms |
307960 KB |
Output is correct |
67 |
Correct |
1599 ms |
417240 KB |
Output is correct |
68 |
Correct |
1358 ms |
338424 KB |
Output is correct |
69 |
Correct |
1278 ms |
303736 KB |
Output is correct |
70 |
Correct |
1590 ms |
417656 KB |
Output is correct |
71 |
Correct |
1375 ms |
338940 KB |
Output is correct |
72 |
Correct |
1343 ms |
307448 KB |
Output is correct |
73 |
Correct |
1641 ms |
417800 KB |
Output is correct |
74 |
Correct |
1406 ms |
339064 KB |
Output is correct |
75 |
Correct |
1344 ms |
307516 KB |
Output is correct |
76 |
Correct |
1659 ms |
418196 KB |
Output is correct |
77 |
Correct |
1603 ms |
417400 KB |
Output is correct |
78 |
Correct |
1623 ms |
418040 KB |
Output is correct |
79 |
Correct |
538 ms |
14712 KB |
Output is correct |
80 |
Correct |
511 ms |
14200 KB |
Output is correct |
81 |
Correct |
509 ms |
14252 KB |
Output is correct |
82 |
Correct |
1644 ms |
416632 KB |
Output is correct |
83 |
Correct |
1683 ms |
402296 KB |
Output is correct |
84 |
Correct |
1601 ms |
416120 KB |
Output is correct |
85 |
Correct |
1627 ms |
401400 KB |
Output is correct |
86 |
Correct |
1597 ms |
416504 KB |
Output is correct |
87 |
Correct |
1648 ms |
402680 KB |
Output is correct |
88 |
Correct |
542 ms |
14584 KB |
Output is correct |
89 |
Correct |
553 ms |
14748 KB |
Output is correct |
90 |
Correct |
510 ms |
14200 KB |
Output is correct |
91 |
Correct |
510 ms |
14252 KB |
Output is correct |
92 |
Correct |
509 ms |
14300 KB |
Output is correct |
93 |
Correct |
499 ms |
14328 KB |
Output is correct |
94 |
Correct |
1151 ms |
259544 KB |
Output is correct |
95 |
Correct |
1002 ms |
212216 KB |
Output is correct |
96 |
Correct |
1103 ms |
258064 KB |
Output is correct |
97 |
Correct |
962 ms |
215848 KB |
Output is correct |
98 |
Correct |
1135 ms |
259344 KB |
Output is correct |
99 |
Correct |
973 ms |
215672 KB |
Output is correct |
100 |
Correct |
596 ms |
14584 KB |
Output is correct |
101 |
Correct |
595 ms |
14716 KB |
Output is correct |
102 |
Correct |
589 ms |
14220 KB |
Output is correct |
103 |
Correct |
567 ms |
14200 KB |
Output is correct |
104 |
Correct |
556 ms |
14200 KB |
Output is correct |
105 |
Correct |
572 ms |
14200 KB |
Output is correct |
106 |
Correct |
1412 ms |
337528 KB |
Output is correct |
107 |
Correct |
1369 ms |
307272 KB |
Output is correct |
108 |
Correct |
1378 ms |
339320 KB |
Output is correct |
109 |
Correct |
1302 ms |
306460 KB |
Output is correct |
110 |
Correct |
1388 ms |
339740 KB |
Output is correct |
111 |
Correct |
1354 ms |
308088 KB |
Output is correct |
112 |
Correct |
546 ms |
14840 KB |
Output is correct |
113 |
Correct |
538 ms |
14840 KB |
Output is correct |
114 |
Correct |
517 ms |
14152 KB |
Output is correct |
115 |
Correct |
522 ms |
14328 KB |
Output is correct |
116 |
Correct |
516 ms |
14200 KB |
Output is correct |
117 |
Correct |
506 ms |
14200 KB |
Output is correct |
118 |
Correct |
1597 ms |
417400 KB |
Output is correct |
119 |
Correct |
1381 ms |
339152 KB |
Output is correct |
120 |
Correct |
1319 ms |
306424 KB |
Output is correct |
121 |
Correct |
1606 ms |
417400 KB |
Output is correct |
122 |
Correct |
1373 ms |
337656 KB |
Output is correct |
123 |
Correct |
1319 ms |
306576 KB |
Output is correct |
124 |
Correct |
1599 ms |
417400 KB |
Output is correct |
125 |
Correct |
1427 ms |
339464 KB |
Output is correct |
126 |
Correct |
1302 ms |
305376 KB |
Output is correct |