#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n, m, q;
const int S = 105;
ii mx[N][S];
int itr[N];
bool ck[N], ck2[N], vis[N];
vector<int> lst[N], nxt[N];
int len[N];
#ifdef local
void process(){
cin >> n >> m >> q;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
lst[y].pb(x);
nxt[x].pb(y);
}
for(int i = 1; i <= n; i++){
vector<ii> vc;
for(auto it : lst[i]){
//cout << "EDGE " << i << " " << it << "\n";
//cout << mx[i][j].se << "\n";
for(int j = 1; j <= 100; j++) vc.pb({mx[it][j].fi + 1, mx[it][j].se});
//vc.pb({1, it});
}
//for(auto it : vc) cout << "OK " << it.fi << " " << it.se << "\n";
sort(vc.begin(), vc.end(), greater<ii>());
int itr = 0;
for(auto it : vc){
//cout << it.se << "\n";
if(vis[it.se]) continue;
// cout << "OKAY " << it.fi << " " << it.se << "\n";
itr++;
if(itr > 100) break;
vis[it.se] = 1;
mx[i][itr] = it;
}
// cout << i << " " << itr << "\n";
if(itr < 100){
itr++;
mx[i][itr] = {0, i};
}
for(int j = 1; j <= 100; j++) vis[mx[i][j].se] = 0;
// cout << i << " ";
// for(int j = 1; j <= itr; j++) cout << mx[i][j].fi << " " << mx[i][j].se << " ";
// cout << "\n";
//priority_queue<ii, vector<ii>, greater<ii>> pq;
}
while(q--){
int s, x;
cin >> s >> x;
vector<int> vc;
for(int i = 1; i <= x; i++){
int y;
cin >> y;
vc.pb(y);
ck2[y] = 1;
}
int answer = -1;
for(int i = 1; i <= 100; i++){
if(mx[s][i].se == 0) continue;
if(!ck2[mx[s][i].se]){
answer = mx[s][i].fi;
break;
}
}
if(answer < 0){
for(int i = 1; i <= n; i++) len[i] = -oo;
len[s] = 0;
for(int i = s - 1; i >= 1; i--){
for(auto it : nxt[i]) len[i] = max(len[i], len[it] + 1);
}
for(int i = 1; i <= s; i++) if(!ck2[i]) answer = max(answer, len[i]);
}
for(auto it : vc) ck2[it] = 0;
cout << answer << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
10 ms |
14352 KB |
Output is correct |
3 |
Correct |
7 ms |
14420 KB |
Output is correct |
4 |
Correct |
7 ms |
14444 KB |
Output is correct |
5 |
Correct |
13 ms |
16116 KB |
Output is correct |
6 |
Correct |
14 ms |
16160 KB |
Output is correct |
7 |
Correct |
14 ms |
16152 KB |
Output is correct |
8 |
Correct |
15 ms |
16128 KB |
Output is correct |
9 |
Correct |
13 ms |
16236 KB |
Output is correct |
10 |
Correct |
13 ms |
16212 KB |
Output is correct |
11 |
Correct |
14 ms |
16104 KB |
Output is correct |
12 |
Correct |
14 ms |
16168 KB |
Output is correct |
13 |
Correct |
15 ms |
16132 KB |
Output is correct |
14 |
Correct |
14 ms |
16252 KB |
Output is correct |
15 |
Correct |
14 ms |
16356 KB |
Output is correct |
16 |
Correct |
17 ms |
16100 KB |
Output is correct |
17 |
Correct |
14 ms |
16136 KB |
Output is correct |
18 |
Correct |
14 ms |
16352 KB |
Output is correct |
19 |
Correct |
13 ms |
16212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
10 ms |
14352 KB |
Output is correct |
3 |
Correct |
7 ms |
14420 KB |
Output is correct |
4 |
Correct |
7 ms |
14444 KB |
Output is correct |
5 |
Correct |
13 ms |
16116 KB |
Output is correct |
6 |
Correct |
14 ms |
16160 KB |
Output is correct |
7 |
Correct |
14 ms |
16152 KB |
Output is correct |
8 |
Correct |
15 ms |
16128 KB |
Output is correct |
9 |
Correct |
13 ms |
16236 KB |
Output is correct |
10 |
Correct |
13 ms |
16212 KB |
Output is correct |
11 |
Correct |
14 ms |
16104 KB |
Output is correct |
12 |
Correct |
14 ms |
16168 KB |
Output is correct |
13 |
Correct |
15 ms |
16132 KB |
Output is correct |
14 |
Correct |
14 ms |
16252 KB |
Output is correct |
15 |
Correct |
14 ms |
16356 KB |
Output is correct |
16 |
Correct |
17 ms |
16100 KB |
Output is correct |
17 |
Correct |
14 ms |
16136 KB |
Output is correct |
18 |
Correct |
14 ms |
16352 KB |
Output is correct |
19 |
Correct |
13 ms |
16212 KB |
Output is correct |
20 |
Correct |
1462 ms |
23532 KB |
Output is correct |
21 |
Correct |
1445 ms |
23580 KB |
Output is correct |
22 |
Correct |
1502 ms |
23512 KB |
Output is correct |
23 |
Correct |
1398 ms |
25836 KB |
Output is correct |
24 |
Correct |
869 ms |
188808 KB |
Output is correct |
25 |
Correct |
856 ms |
188780 KB |
Output is correct |
26 |
Correct |
874 ms |
189448 KB |
Output is correct |
27 |
Correct |
571 ms |
190476 KB |
Output is correct |
28 |
Correct |
630 ms |
190524 KB |
Output is correct |
29 |
Correct |
554 ms |
191096 KB |
Output is correct |
30 |
Correct |
608 ms |
189768 KB |
Output is correct |
31 |
Correct |
698 ms |
189832 KB |
Output is correct |
32 |
Correct |
608 ms |
190400 KB |
Output is correct |
33 |
Correct |
738 ms |
189940 KB |
Output is correct |
34 |
Correct |
718 ms |
190276 KB |
Output is correct |
35 |
Correct |
661 ms |
189860 KB |
Output is correct |
36 |
Correct |
634 ms |
189916 KB |
Output is correct |
37 |
Correct |
791 ms |
190228 KB |
Output is correct |
38 |
Correct |
632 ms |
190536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
10 ms |
14352 KB |
Output is correct |
3 |
Correct |
7 ms |
14420 KB |
Output is correct |
4 |
Correct |
7 ms |
14444 KB |
Output is correct |
5 |
Correct |
13 ms |
16116 KB |
Output is correct |
6 |
Correct |
14 ms |
16160 KB |
Output is correct |
7 |
Correct |
14 ms |
16152 KB |
Output is correct |
8 |
Correct |
15 ms |
16128 KB |
Output is correct |
9 |
Correct |
13 ms |
16236 KB |
Output is correct |
10 |
Correct |
13 ms |
16212 KB |
Output is correct |
11 |
Correct |
14 ms |
16104 KB |
Output is correct |
12 |
Correct |
14 ms |
16168 KB |
Output is correct |
13 |
Correct |
15 ms |
16132 KB |
Output is correct |
14 |
Correct |
14 ms |
16252 KB |
Output is correct |
15 |
Correct |
14 ms |
16356 KB |
Output is correct |
16 |
Correct |
17 ms |
16100 KB |
Output is correct |
17 |
Correct |
14 ms |
16136 KB |
Output is correct |
18 |
Correct |
14 ms |
16352 KB |
Output is correct |
19 |
Correct |
13 ms |
16212 KB |
Output is correct |
20 |
Correct |
1462 ms |
23532 KB |
Output is correct |
21 |
Correct |
1445 ms |
23580 KB |
Output is correct |
22 |
Correct |
1502 ms |
23512 KB |
Output is correct |
23 |
Correct |
1398 ms |
25836 KB |
Output is correct |
24 |
Correct |
869 ms |
188808 KB |
Output is correct |
25 |
Correct |
856 ms |
188780 KB |
Output is correct |
26 |
Correct |
874 ms |
189448 KB |
Output is correct |
27 |
Correct |
571 ms |
190476 KB |
Output is correct |
28 |
Correct |
630 ms |
190524 KB |
Output is correct |
29 |
Correct |
554 ms |
191096 KB |
Output is correct |
30 |
Correct |
608 ms |
189768 KB |
Output is correct |
31 |
Correct |
698 ms |
189832 KB |
Output is correct |
32 |
Correct |
608 ms |
190400 KB |
Output is correct |
33 |
Correct |
738 ms |
189940 KB |
Output is correct |
34 |
Correct |
718 ms |
190276 KB |
Output is correct |
35 |
Correct |
661 ms |
189860 KB |
Output is correct |
36 |
Correct |
634 ms |
189916 KB |
Output is correct |
37 |
Correct |
791 ms |
190228 KB |
Output is correct |
38 |
Correct |
632 ms |
190536 KB |
Output is correct |
39 |
Correct |
885 ms |
189604 KB |
Output is correct |
40 |
Correct |
836 ms |
188600 KB |
Output is correct |
41 |
Correct |
835 ms |
188524 KB |
Output is correct |
42 |
Correct |
833 ms |
188568 KB |
Output is correct |
43 |
Correct |
847 ms |
188736 KB |
Output is correct |
44 |
Correct |
1498 ms |
24032 KB |
Output is correct |
45 |
Correct |
1486 ms |
23684 KB |
Output is correct |
46 |
Correct |
1466 ms |
23736 KB |
Output is correct |
47 |
Correct |
1464 ms |
23552 KB |
Output is correct |
48 |
Correct |
1458 ms |
23552 KB |
Output is correct |
49 |
Correct |
580 ms |
191880 KB |
Output is correct |
50 |
Correct |
908 ms |
190672 KB |
Output is correct |
51 |
Correct |
1439 ms |
23876 KB |
Output is correct |
52 |
Correct |
1497 ms |
23620 KB |
Output is correct |
53 |
Correct |
665 ms |
191120 KB |
Output is correct |
54 |
Correct |
764 ms |
190340 KB |
Output is correct |
55 |
Correct |
755 ms |
190180 KB |
Output is correct |
56 |
Correct |
739 ms |
190324 KB |
Output is correct |
57 |
Correct |
1477 ms |
23820 KB |
Output is correct |
58 |
Correct |
1519 ms |
24112 KB |
Output is correct |
59 |
Correct |
1590 ms |
23872 KB |
Output is correct |
60 |
Correct |
1518 ms |
24164 KB |
Output is correct |
61 |
Correct |
617 ms |
190632 KB |
Output is correct |
62 |
Correct |
729 ms |
190156 KB |
Output is correct |
63 |
Correct |
781 ms |
190264 KB |
Output is correct |
64 |
Correct |
724 ms |
190760 KB |
Output is correct |
65 |
Correct |
800 ms |
190212 KB |
Output is correct |
66 |
Correct |
752 ms |
190216 KB |
Output is correct |
67 |
Correct |
865 ms |
190696 KB |
Output is correct |
68 |
Correct |
876 ms |
190164 KB |
Output is correct |
69 |
Correct |
737 ms |
190132 KB |
Output is correct |
70 |
Correct |
582 ms |
191108 KB |
Output is correct |
71 |
Correct |
637 ms |
190704 KB |
Output is correct |
72 |
Correct |
740 ms |
190372 KB |
Output is correct |
73 |
Correct |
563 ms |
190800 KB |
Output is correct |
74 |
Correct |
653 ms |
190376 KB |
Output is correct |
75 |
Correct |
736 ms |
190272 KB |
Output is correct |
76 |
Correct |
596 ms |
191536 KB |
Output is correct |
77 |
Correct |
546 ms |
190172 KB |
Output is correct |
78 |
Correct |
574 ms |
190592 KB |
Output is correct |
79 |
Correct |
1467 ms |
23960 KB |
Output is correct |
80 |
Correct |
1441 ms |
23712 KB |
Output is correct |
81 |
Correct |
1457 ms |
23548 KB |
Output is correct |
82 |
Correct |
621 ms |
190824 KB |
Output is correct |
83 |
Correct |
754 ms |
190628 KB |
Output is correct |
84 |
Correct |
585 ms |
189604 KB |
Output is correct |
85 |
Correct |
709 ms |
189388 KB |
Output is correct |
86 |
Correct |
584 ms |
189848 KB |
Output is correct |
87 |
Correct |
708 ms |
189852 KB |
Output is correct |
88 |
Correct |
1479 ms |
24060 KB |
Output is correct |
89 |
Correct |
1450 ms |
24080 KB |
Output is correct |
90 |
Correct |
1469 ms |
23852 KB |
Output is correct |
91 |
Correct |
1436 ms |
23788 KB |
Output is correct |
92 |
Correct |
1458 ms |
23600 KB |
Output is correct |
93 |
Correct |
1432 ms |
23628 KB |
Output is correct |
94 |
Correct |
693 ms |
190876 KB |
Output is correct |
95 |
Correct |
745 ms |
190880 KB |
Output is correct |
96 |
Correct |
650 ms |
189676 KB |
Output is correct |
97 |
Correct |
731 ms |
190260 KB |
Output is correct |
98 |
Correct |
657 ms |
189972 KB |
Output is correct |
99 |
Correct |
702 ms |
190460 KB |
Output is correct |
100 |
Correct |
1420 ms |
24676 KB |
Output is correct |
101 |
Correct |
1371 ms |
25992 KB |
Output is correct |
102 |
Correct |
1417 ms |
24720 KB |
Output is correct |
103 |
Correct |
1367 ms |
25956 KB |
Output is correct |
104 |
Correct |
1371 ms |
24512 KB |
Output is correct |
105 |
Correct |
1356 ms |
25776 KB |
Output is correct |
106 |
Correct |
656 ms |
190880 KB |
Output is correct |
107 |
Correct |
766 ms |
190944 KB |
Output is correct |
108 |
Correct |
630 ms |
189628 KB |
Output is correct |
109 |
Correct |
707 ms |
190156 KB |
Output is correct |
110 |
Correct |
670 ms |
190024 KB |
Output is correct |
111 |
Correct |
731 ms |
190284 KB |
Output is correct |
112 |
Correct |
1474 ms |
24004 KB |
Output is correct |
113 |
Correct |
1455 ms |
24280 KB |
Output is correct |
114 |
Correct |
1468 ms |
23728 KB |
Output is correct |
115 |
Correct |
1466 ms |
24200 KB |
Output is correct |
116 |
Correct |
1454 ms |
23524 KB |
Output is correct |
117 |
Correct |
1434 ms |
24348 KB |
Output is correct |
118 |
Correct |
563 ms |
190660 KB |
Output is correct |
119 |
Correct |
633 ms |
190132 KB |
Output is correct |
120 |
Correct |
716 ms |
190256 KB |
Output is correct |
121 |
Correct |
545 ms |
189892 KB |
Output is correct |
122 |
Correct |
642 ms |
190076 KB |
Output is correct |
123 |
Correct |
737 ms |
190232 KB |
Output is correct |
124 |
Correct |
554 ms |
190548 KB |
Output is correct |
125 |
Correct |
626 ms |
189332 KB |
Output is correct |
126 |
Correct |
746 ms |
190244 KB |
Output is correct |