#include<bits/stdc++.h>
using namespace std;
const int mx=500000;
const int mx2=2e4+19;
typedef long long ll;
const int mod=998244353 ;
const int SQ=350;
const ll inf=1e9+10;
int n,m,q;
vector<int>adj[mx]; vector <pair <int, int>>f[mx];int vis[mx];int vis2[mx];int cur=1;int dp[mx];
vector< pair<int,int>> merge(vector< pair < int ,int > > &l, vector< pair < int,int > >&r){
int left=0; int right=0; int lsize=l.size(); int rsize=r.size();
vector<pair<int,int>>ret;
while(ret.size()<SQ&&(left<lsize||right<rsize)){
pair<int,int>ok;
if(left==lsize){
ok=r[right];
ok.first++;
right++;
}else if(right==rsize){
ok=l[left];
left++;
}else if(l[left].first>r[right].first+1){
ok=l[left];
left++;
}else{
ok=r[right];
right++;
ok.first++;
}
if(vis[ok.second]==cur){continue;}
vis[ok.second]=cur;
ret.push_back(ok);
}
return ret;
}
int main(){
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
adj[y].push_back(x);
}
for(int i=1;i<=n;i++){
f[i].push_back({0,i});
for(auto&j:adj[i]){
f[i] = merge(f[i], f[j]);
cur++;
}
}
/*
cout<<"TEST \n";
for(auto it:f[4]){
cout<<it.second<<" "<<it.first<<endl;
}
cout<<endl;
*/
while(q--){
int idx,y;
cin>>idx>>y;
int arr[y];
for(int j=0;j<y;j++){
cin>>arr[j];
vis2[arr[j]]=1;
}
if(y<SQ){
int ans=-1;
for(auto it:f[idx]){
if(vis2[it.second]){continue;}
ans=max(ans,it.first);
break;
}
cout<<ans<<"\n";
}else{
int ans=-1;
vector<int>dis(idx+5,-inf);
dis[idx]=0;
for(int j=idx;j>=1;j--){
for(auto it:adj[j]){
dis[it]=max(dis[it],dis[j]+1);
}
if(vis2[j]){}else{ ans=max(ans,dis[j]); }
}
cout<<ans<<"\n";
}
for(int j=0;j<y;j++){
vis2[arr[j]]=0;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
24288 KB |
Output is correct |
6 |
Correct |
15 ms |
24264 KB |
Output is correct |
7 |
Correct |
15 ms |
24148 KB |
Output is correct |
8 |
Correct |
20 ms |
27236 KB |
Output is correct |
9 |
Correct |
21 ms |
27092 KB |
Output is correct |
10 |
Correct |
23 ms |
27340 KB |
Output is correct |
11 |
Correct |
24 ms |
26792 KB |
Output is correct |
12 |
Correct |
16 ms |
25172 KB |
Output is correct |
13 |
Correct |
20 ms |
26568 KB |
Output is correct |
14 |
Correct |
19 ms |
25752 KB |
Output is correct |
15 |
Correct |
20 ms |
24696 KB |
Output is correct |
16 |
Correct |
20 ms |
25684 KB |
Output is correct |
17 |
Correct |
19 ms |
25980 KB |
Output is correct |
18 |
Correct |
18 ms |
24916 KB |
Output is correct |
19 |
Correct |
19 ms |
26008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
24288 KB |
Output is correct |
6 |
Correct |
15 ms |
24264 KB |
Output is correct |
7 |
Correct |
15 ms |
24148 KB |
Output is correct |
8 |
Correct |
20 ms |
27236 KB |
Output is correct |
9 |
Correct |
21 ms |
27092 KB |
Output is correct |
10 |
Correct |
23 ms |
27340 KB |
Output is correct |
11 |
Correct |
24 ms |
26792 KB |
Output is correct |
12 |
Correct |
16 ms |
25172 KB |
Output is correct |
13 |
Correct |
20 ms |
26568 KB |
Output is correct |
14 |
Correct |
19 ms |
25752 KB |
Output is correct |
15 |
Correct |
20 ms |
24696 KB |
Output is correct |
16 |
Correct |
20 ms |
25684 KB |
Output is correct |
17 |
Correct |
19 ms |
25980 KB |
Output is correct |
18 |
Correct |
18 ms |
24916 KB |
Output is correct |
19 |
Correct |
19 ms |
26008 KB |
Output is correct |
20 |
Correct |
887 ms |
29792 KB |
Output is correct |
21 |
Correct |
799 ms |
29728 KB |
Output is correct |
22 |
Correct |
826 ms |
29848 KB |
Output is correct |
23 |
Correct |
925 ms |
30108 KB |
Output is correct |
24 |
Correct |
882 ms |
274140 KB |
Output is correct |
25 |
Correct |
877 ms |
285740 KB |
Output is correct |
26 |
Correct |
875 ms |
284488 KB |
Output is correct |
27 |
Correct |
1061 ms |
432112 KB |
Output is correct |
28 |
Correct |
1067 ms |
432040 KB |
Output is correct |
29 |
Correct |
1055 ms |
432020 KB |
Output is correct |
30 |
Correct |
1075 ms |
431524 KB |
Output is correct |
31 |
Correct |
1024 ms |
417364 KB |
Output is correct |
32 |
Correct |
1068 ms |
431232 KB |
Output is correct |
33 |
Correct |
850 ms |
274248 KB |
Output is correct |
34 |
Correct |
801 ms |
228428 KB |
Output is correct |
35 |
Correct |
840 ms |
272480 KB |
Output is correct |
36 |
Correct |
980 ms |
353216 KB |
Output is correct |
37 |
Correct |
923 ms |
321448 KB |
Output is correct |
38 |
Correct |
983 ms |
354080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
24288 KB |
Output is correct |
6 |
Correct |
15 ms |
24264 KB |
Output is correct |
7 |
Correct |
15 ms |
24148 KB |
Output is correct |
8 |
Correct |
20 ms |
27236 KB |
Output is correct |
9 |
Correct |
21 ms |
27092 KB |
Output is correct |
10 |
Correct |
23 ms |
27340 KB |
Output is correct |
11 |
Correct |
24 ms |
26792 KB |
Output is correct |
12 |
Correct |
16 ms |
25172 KB |
Output is correct |
13 |
Correct |
20 ms |
26568 KB |
Output is correct |
14 |
Correct |
19 ms |
25752 KB |
Output is correct |
15 |
Correct |
20 ms |
24696 KB |
Output is correct |
16 |
Correct |
20 ms |
25684 KB |
Output is correct |
17 |
Correct |
19 ms |
25980 KB |
Output is correct |
18 |
Correct |
18 ms |
24916 KB |
Output is correct |
19 |
Correct |
19 ms |
26008 KB |
Output is correct |
20 |
Correct |
887 ms |
29792 KB |
Output is correct |
21 |
Correct |
799 ms |
29728 KB |
Output is correct |
22 |
Correct |
826 ms |
29848 KB |
Output is correct |
23 |
Correct |
925 ms |
30108 KB |
Output is correct |
24 |
Correct |
882 ms |
274140 KB |
Output is correct |
25 |
Correct |
877 ms |
285740 KB |
Output is correct |
26 |
Correct |
875 ms |
284488 KB |
Output is correct |
27 |
Correct |
1061 ms |
432112 KB |
Output is correct |
28 |
Correct |
1067 ms |
432040 KB |
Output is correct |
29 |
Correct |
1055 ms |
432020 KB |
Output is correct |
30 |
Correct |
1075 ms |
431524 KB |
Output is correct |
31 |
Correct |
1024 ms |
417364 KB |
Output is correct |
32 |
Correct |
1068 ms |
431232 KB |
Output is correct |
33 |
Correct |
850 ms |
274248 KB |
Output is correct |
34 |
Correct |
801 ms |
228428 KB |
Output is correct |
35 |
Correct |
840 ms |
272480 KB |
Output is correct |
36 |
Correct |
980 ms |
353216 KB |
Output is correct |
37 |
Correct |
923 ms |
321448 KB |
Output is correct |
38 |
Correct |
983 ms |
354080 KB |
Output is correct |
39 |
Correct |
1064 ms |
278204 KB |
Output is correct |
40 |
Correct |
914 ms |
280032 KB |
Output is correct |
41 |
Correct |
920 ms |
282568 KB |
Output is correct |
42 |
Correct |
993 ms |
280884 KB |
Output is correct |
43 |
Correct |
874 ms |
280296 KB |
Output is correct |
44 |
Correct |
991 ms |
31268 KB |
Output is correct |
45 |
Correct |
844 ms |
30372 KB |
Output is correct |
46 |
Correct |
822 ms |
30292 KB |
Output is correct |
47 |
Correct |
843 ms |
30044 KB |
Output is correct |
48 |
Correct |
828 ms |
29804 KB |
Output is correct |
49 |
Correct |
1249 ms |
432496 KB |
Output is correct |
50 |
Correct |
1073 ms |
431280 KB |
Output is correct |
51 |
Correct |
934 ms |
31100 KB |
Output is correct |
52 |
Correct |
799 ms |
30108 KB |
Output is correct |
53 |
Correct |
1193 ms |
352156 KB |
Output is correct |
54 |
Correct |
1093 ms |
322060 KB |
Output is correct |
55 |
Correct |
1008 ms |
351624 KB |
Output is correct |
56 |
Correct |
929 ms |
322080 KB |
Output is correct |
57 |
Correct |
976 ms |
30892 KB |
Output is correct |
58 |
Correct |
1018 ms |
31052 KB |
Output is correct |
59 |
Correct |
822 ms |
30144 KB |
Output is correct |
60 |
Correct |
827 ms |
30000 KB |
Output is correct |
61 |
Correct |
1159 ms |
431700 KB |
Output is correct |
62 |
Correct |
1106 ms |
353352 KB |
Output is correct |
63 |
Correct |
973 ms |
320776 KB |
Output is correct |
64 |
Correct |
1154 ms |
431780 KB |
Output is correct |
65 |
Correct |
1037 ms |
351772 KB |
Output is correct |
66 |
Correct |
991 ms |
322524 KB |
Output is correct |
67 |
Correct |
1053 ms |
431292 KB |
Output is correct |
68 |
Correct |
978 ms |
352912 KB |
Output is correct |
69 |
Correct |
890 ms |
318524 KB |
Output is correct |
70 |
Correct |
1071 ms |
431844 KB |
Output is correct |
71 |
Correct |
977 ms |
353600 KB |
Output is correct |
72 |
Correct |
934 ms |
322336 KB |
Output is correct |
73 |
Correct |
1114 ms |
431884 KB |
Output is correct |
74 |
Correct |
999 ms |
353468 KB |
Output is correct |
75 |
Correct |
964 ms |
322212 KB |
Output is correct |
76 |
Correct |
1242 ms |
433268 KB |
Output is correct |
77 |
Correct |
1092 ms |
431812 KB |
Output is correct |
78 |
Correct |
1087 ms |
432392 KB |
Output is correct |
79 |
Correct |
947 ms |
31164 KB |
Output is correct |
80 |
Correct |
795 ms |
30160 KB |
Output is correct |
81 |
Correct |
788 ms |
29820 KB |
Output is correct |
82 |
Correct |
1281 ms |
432728 KB |
Output is correct |
83 |
Correct |
1240 ms |
418588 KB |
Output is correct |
84 |
Correct |
1076 ms |
431356 KB |
Output is correct |
85 |
Correct |
1037 ms |
416776 KB |
Output is correct |
86 |
Correct |
1084 ms |
431752 KB |
Output is correct |
87 |
Correct |
1054 ms |
418444 KB |
Output is correct |
88 |
Correct |
1028 ms |
31208 KB |
Output is correct |
89 |
Correct |
997 ms |
31072 KB |
Output is correct |
90 |
Correct |
861 ms |
30308 KB |
Output is correct |
91 |
Correct |
849 ms |
30196 KB |
Output is correct |
92 |
Correct |
832 ms |
29828 KB |
Output is correct |
93 |
Correct |
812 ms |
29880 KB |
Output is correct |
94 |
Correct |
1035 ms |
275544 KB |
Output is correct |
95 |
Correct |
979 ms |
227992 KB |
Output is correct |
96 |
Correct |
869 ms |
273100 KB |
Output is correct |
97 |
Correct |
800 ms |
231048 KB |
Output is correct |
98 |
Correct |
871 ms |
274412 KB |
Output is correct |
99 |
Correct |
795 ms |
230644 KB |
Output is correct |
100 |
Correct |
1123 ms |
31324 KB |
Output is correct |
101 |
Correct |
1080 ms |
31328 KB |
Output is correct |
102 |
Correct |
933 ms |
30332 KB |
Output is correct |
103 |
Correct |
970 ms |
30280 KB |
Output is correct |
104 |
Correct |
918 ms |
29876 KB |
Output is correct |
105 |
Correct |
912 ms |
29828 KB |
Output is correct |
106 |
Correct |
1145 ms |
353216 KB |
Output is correct |
107 |
Correct |
1120 ms |
323012 KB |
Output is correct |
108 |
Correct |
981 ms |
354288 KB |
Output is correct |
109 |
Correct |
918 ms |
321596 KB |
Output is correct |
110 |
Correct |
1006 ms |
355112 KB |
Output is correct |
111 |
Correct |
957 ms |
322960 KB |
Output is correct |
112 |
Correct |
978 ms |
31148 KB |
Output is correct |
113 |
Correct |
1012 ms |
31196 KB |
Output is correct |
114 |
Correct |
840 ms |
30324 KB |
Output is correct |
115 |
Correct |
838 ms |
30132 KB |
Output is correct |
116 |
Correct |
818 ms |
29868 KB |
Output is correct |
117 |
Correct |
820 ms |
29864 KB |
Output is correct |
118 |
Correct |
1056 ms |
431160 KB |
Output is correct |
119 |
Correct |
1010 ms |
353580 KB |
Output is correct |
120 |
Correct |
922 ms |
320768 KB |
Output is correct |
121 |
Correct |
1082 ms |
431240 KB |
Output is correct |
122 |
Correct |
1002 ms |
352088 KB |
Output is correct |
123 |
Correct |
938 ms |
321176 KB |
Output is correct |
124 |
Correct |
1063 ms |
431296 KB |
Output is correct |
125 |
Correct |
963 ms |
353760 KB |
Output is correct |
126 |
Correct |
967 ms |
319968 KB |
Output is correct |