#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 110;
int w,e;
vector<pair<int,int>> res;
int n,m,q;
bool blocked[MAXN];
int dp[MAXN];
vector<int> v1[MAXN];
vector<int> v1rev[MAXN];
vector<pair<int,int>> temp[MAXN];
vector<int> hold;
int m1[MAXN];
vector<pair<int,int>> c;
void merge(vector<pair<int,int>> &a,vector<pair<int,int>> b){
c.clear();
int ind = 0;
for(int i=0;i<b.size();i++){
while(ind<a.size() && a[ind].first>=b[i].first+1){
c.push_back(make_pair(a[ind].first,a[ind].second));
ind++;
}
c.push_back(make_pair(b[i].first+1,b[i].second));
}
while(ind<a.size()){
c.push_back(make_pair(a[ind].first,a[ind].second));
ind++;
}
int cnt = 0;
for(int i=0;i<c.size();i++){
//cout<<e<<" "<<w<<" "<<c[i].first<<" "<<c[i].second<<endl;
if(m1[c[i].second]){
m1[c[i].second] = 0;
}
}
b.clear();
for(int i=0;i<c.size() && cnt<sqrtn;i++){
if(!m1[c[i].second]){
//if node not seen yet, add it to possible nodes,set it to the distance
m1[c[i].second] = c[i].first;
b.push_back(make_pair(c[i].second,0));
cnt++;
}else{
m1[c[i].second] = max(m1[c[i].second],c[i].first);
}
}
a.clear();
for(auto x:b){
a.push_back(make_pair(m1[x.first],x.first));
}
while(a.size()>sqrtn){
a.pop_back();
}
}
int dodp(int t){
for(int i=1;i<=n;i++){
blocked[i] = false;
dp[i] = 0;
}
for(int i=0;i<hold.size();i++){
blocked[hold[i]] = true;
}
for(int i=1;i<=n;i++){
if(blocked[i]){
dp[i] = -1e9;
}else{
dp[i] = 0;
}
for(int x:v1rev[i]){
dp[i] = max(dp[i],dp[x]+1);
}
if(i==t){
return max(-1,dp[t]);
}
//cout<<123<<" "<<dp[i]<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
v1[u].push_back(v);
v1rev[v].push_back(u);
//v1rev -> backwards
}
for(int i=1;i<=n;i++){
temp[i].push_back(make_pair(0,i));
for(int x:v1rev[i]){
//temp[v].push_back(make_pair(1,1));
merge(temp[i],temp[x]);
//Keep merging temp[i] with nodes which connect to it to find furthest nodes
}
//cout<<temp[i][0].first<<endl;
}
// cout<<123<<endl;
for(int i=1;i<=n;i++){
m1[i] = -1;
}
//cout<<cnt3<<endl;
//cout<<temp[544].size()<<endl;
while(q--){
int t,c;
cin>>t>>c;
// cout<<t<<" "<<c<<endl;
hold.clear();
// set<int> s1;
for(int i=1;i<=c;i++){
int x;
cin>>x;
hold.push_back(x);
m1[x] = q;
//s1.insert(x);
}
//sort(hold.begin(),hold.end());
if(hold.size()>=sqrtn){
cout<<dodp(t)<<"\n";
}else{
bool ok = false;
//cout<<t<<" "<<c<<endl;
if(hold.size() == 0){
if(temp[t].size()){
cout<<temp[t][0].first<<"\n";
}else{
cout<<-1<<"\n";
}
continue;
}
// sort(hold.begin(),hold.end());
for(auto x:temp[t]){
// cout<<t<<" "<<c<<" "<<x.first<<" "<<x.second<<endl;
if(m1[x.second]!=q){
cout<<x.first<<"\n";
ok = true;
break;
}
}
if(!ok){
cout<<-1<<"\n";
}
}
}
}
Compilation message
bitaro.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
bitaro.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<b.size();i++){
~^~~~~~~~~
bitaro.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<a.size() && a[ind].first>=b[i].first+1){
~~~^~~~~~~~~
bitaro.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<a.size()){
~~~^~~~~~~~~
bitaro.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<c.size();i++){
~^~~~~~~~~
bitaro.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<c.size() && cnt<sqrtn;i++){
~^~~~~~~~~
bitaro.cpp: In function 'int dodp(int)':
bitaro.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<hold.size();i++){
~^~~~~~~~~~~~
bitaro.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
21 ms |
14976 KB |
Output is correct |
6 |
Correct |
17 ms |
14976 KB |
Output is correct |
7 |
Correct |
17 ms |
14976 KB |
Output is correct |
8 |
Correct |
22 ms |
15488 KB |
Output is correct |
9 |
Correct |
28 ms |
15480 KB |
Output is correct |
10 |
Correct |
25 ms |
15488 KB |
Output is correct |
11 |
Correct |
24 ms |
15488 KB |
Output is correct |
12 |
Correct |
23 ms |
15208 KB |
Output is correct |
13 |
Correct |
24 ms |
15488 KB |
Output is correct |
14 |
Correct |
24 ms |
15104 KB |
Output is correct |
15 |
Correct |
22 ms |
14848 KB |
Output is correct |
16 |
Correct |
20 ms |
15104 KB |
Output is correct |
17 |
Correct |
21 ms |
15232 KB |
Output is correct |
18 |
Correct |
23 ms |
15104 KB |
Output is correct |
19 |
Correct |
25 ms |
15232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
21 ms |
14976 KB |
Output is correct |
6 |
Correct |
17 ms |
14976 KB |
Output is correct |
7 |
Correct |
17 ms |
14976 KB |
Output is correct |
8 |
Correct |
22 ms |
15488 KB |
Output is correct |
9 |
Correct |
28 ms |
15480 KB |
Output is correct |
10 |
Correct |
25 ms |
15488 KB |
Output is correct |
11 |
Correct |
24 ms |
15488 KB |
Output is correct |
12 |
Correct |
23 ms |
15208 KB |
Output is correct |
13 |
Correct |
24 ms |
15488 KB |
Output is correct |
14 |
Correct |
24 ms |
15104 KB |
Output is correct |
15 |
Correct |
22 ms |
14848 KB |
Output is correct |
16 |
Correct |
20 ms |
15104 KB |
Output is correct |
17 |
Correct |
21 ms |
15232 KB |
Output is correct |
18 |
Correct |
23 ms |
15104 KB |
Output is correct |
19 |
Correct |
25 ms |
15232 KB |
Output is correct |
20 |
Correct |
1054 ms |
17764 KB |
Output is correct |
21 |
Correct |
1014 ms |
17680 KB |
Output is correct |
22 |
Correct |
1008 ms |
17784 KB |
Output is correct |
23 |
Correct |
1053 ms |
17788 KB |
Output is correct |
24 |
Correct |
1134 ms |
99220 KB |
Output is correct |
25 |
Correct |
1112 ms |
100572 KB |
Output is correct |
26 |
Correct |
1110 ms |
100380 KB |
Output is correct |
27 |
Correct |
1201 ms |
124148 KB |
Output is correct |
28 |
Correct |
1240 ms |
124148 KB |
Output is correct |
29 |
Correct |
1162 ms |
124128 KB |
Output is correct |
30 |
Correct |
1116 ms |
123256 KB |
Output is correct |
31 |
Correct |
1130 ms |
121644 KB |
Output is correct |
32 |
Correct |
1125 ms |
123380 KB |
Output is correct |
33 |
Correct |
927 ms |
85748 KB |
Output is correct |
34 |
Correct |
907 ms |
78836 KB |
Output is correct |
35 |
Correct |
958 ms |
85368 KB |
Output is correct |
36 |
Correct |
1057 ms |
104696 KB |
Output is correct |
37 |
Correct |
1033 ms |
100052 KB |
Output is correct |
38 |
Correct |
1039 ms |
104776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
21 ms |
14976 KB |
Output is correct |
6 |
Correct |
17 ms |
14976 KB |
Output is correct |
7 |
Correct |
17 ms |
14976 KB |
Output is correct |
8 |
Correct |
22 ms |
15488 KB |
Output is correct |
9 |
Correct |
28 ms |
15480 KB |
Output is correct |
10 |
Correct |
25 ms |
15488 KB |
Output is correct |
11 |
Correct |
24 ms |
15488 KB |
Output is correct |
12 |
Correct |
23 ms |
15208 KB |
Output is correct |
13 |
Correct |
24 ms |
15488 KB |
Output is correct |
14 |
Correct |
24 ms |
15104 KB |
Output is correct |
15 |
Correct |
22 ms |
14848 KB |
Output is correct |
16 |
Correct |
20 ms |
15104 KB |
Output is correct |
17 |
Correct |
21 ms |
15232 KB |
Output is correct |
18 |
Correct |
23 ms |
15104 KB |
Output is correct |
19 |
Correct |
25 ms |
15232 KB |
Output is correct |
20 |
Correct |
1054 ms |
17764 KB |
Output is correct |
21 |
Correct |
1014 ms |
17680 KB |
Output is correct |
22 |
Correct |
1008 ms |
17784 KB |
Output is correct |
23 |
Correct |
1053 ms |
17788 KB |
Output is correct |
24 |
Correct |
1134 ms |
99220 KB |
Output is correct |
25 |
Correct |
1112 ms |
100572 KB |
Output is correct |
26 |
Correct |
1110 ms |
100380 KB |
Output is correct |
27 |
Correct |
1201 ms |
124148 KB |
Output is correct |
28 |
Correct |
1240 ms |
124148 KB |
Output is correct |
29 |
Correct |
1162 ms |
124128 KB |
Output is correct |
30 |
Correct |
1116 ms |
123256 KB |
Output is correct |
31 |
Correct |
1130 ms |
121644 KB |
Output is correct |
32 |
Correct |
1125 ms |
123380 KB |
Output is correct |
33 |
Correct |
927 ms |
85748 KB |
Output is correct |
34 |
Correct |
907 ms |
78836 KB |
Output is correct |
35 |
Correct |
958 ms |
85368 KB |
Output is correct |
36 |
Correct |
1057 ms |
104696 KB |
Output is correct |
37 |
Correct |
1033 ms |
100052 KB |
Output is correct |
38 |
Correct |
1039 ms |
104776 KB |
Output is correct |
39 |
Correct |
1147 ms |
99036 KB |
Output is correct |
40 |
Correct |
1102 ms |
99832 KB |
Output is correct |
41 |
Correct |
1252 ms |
100344 KB |
Output is correct |
42 |
Correct |
1207 ms |
99832 KB |
Output is correct |
43 |
Correct |
1169 ms |
99936 KB |
Output is correct |
44 |
Correct |
1064 ms |
18424 KB |
Output is correct |
45 |
Correct |
1020 ms |
18040 KB |
Output is correct |
46 |
Correct |
1044 ms |
18168 KB |
Output is correct |
47 |
Correct |
1033 ms |
18040 KB |
Output is correct |
48 |
Correct |
1008 ms |
17912 KB |
Output is correct |
49 |
Correct |
1216 ms |
124152 KB |
Output is correct |
50 |
Correct |
1359 ms |
123836 KB |
Output is correct |
51 |
Correct |
1087 ms |
18296 KB |
Output is correct |
52 |
Correct |
1031 ms |
17784 KB |
Output is correct |
53 |
Correct |
1121 ms |
103928 KB |
Output is correct |
54 |
Correct |
1086 ms |
99704 KB |
Output is correct |
55 |
Correct |
1260 ms |
104316 KB |
Output is correct |
56 |
Correct |
1210 ms |
100008 KB |
Output is correct |
57 |
Correct |
1037 ms |
18168 KB |
Output is correct |
58 |
Correct |
1042 ms |
18340 KB |
Output is correct |
59 |
Correct |
1033 ms |
17784 KB |
Output is correct |
60 |
Correct |
1026 ms |
17912 KB |
Output is correct |
61 |
Correct |
1244 ms |
123768 KB |
Output is correct |
62 |
Correct |
1141 ms |
104576 KB |
Output is correct |
63 |
Correct |
1136 ms |
99320 KB |
Output is correct |
64 |
Correct |
1416 ms |
123900 KB |
Output is correct |
65 |
Correct |
1315 ms |
104312 KB |
Output is correct |
66 |
Correct |
1317 ms |
100216 KB |
Output is correct |
67 |
Correct |
1577 ms |
123864 KB |
Output is correct |
68 |
Correct |
1469 ms |
107128 KB |
Output is correct |
69 |
Correct |
1497 ms |
102008 KB |
Output is correct |
70 |
Correct |
1195 ms |
126456 KB |
Output is correct |
71 |
Correct |
1076 ms |
107256 KB |
Output is correct |
72 |
Correct |
1067 ms |
102392 KB |
Output is correct |
73 |
Correct |
1208 ms |
126504 KB |
Output is correct |
74 |
Correct |
1116 ms |
107080 KB |
Output is correct |
75 |
Correct |
1084 ms |
102392 KB |
Output is correct |
76 |
Correct |
1244 ms |
126688 KB |
Output is correct |
77 |
Correct |
1551 ms |
126712 KB |
Output is correct |
78 |
Correct |
1198 ms |
126840 KB |
Output is correct |
79 |
Correct |
1032 ms |
20728 KB |
Output is correct |
80 |
Correct |
1057 ms |
19704 KB |
Output is correct |
81 |
Correct |
1000 ms |
19460 KB |
Output is correct |
82 |
Correct |
1197 ms |
125816 KB |
Output is correct |
83 |
Correct |
1203 ms |
124152 KB |
Output is correct |
84 |
Correct |
1496 ms |
125864 KB |
Output is correct |
85 |
Correct |
1586 ms |
123944 KB |
Output is correct |
86 |
Correct |
1135 ms |
125944 KB |
Output is correct |
87 |
Correct |
1154 ms |
124360 KB |
Output is correct |
88 |
Correct |
1043 ms |
20656 KB |
Output is correct |
89 |
Correct |
1034 ms |
20612 KB |
Output is correct |
90 |
Correct |
1069 ms |
19740 KB |
Output is correct |
91 |
Correct |
1069 ms |
19704 KB |
Output is correct |
92 |
Correct |
1006 ms |
19396 KB |
Output is correct |
93 |
Correct |
1008 ms |
19320 KB |
Output is correct |
94 |
Correct |
984 ms |
88192 KB |
Output is correct |
95 |
Correct |
949 ms |
80504 KB |
Output is correct |
96 |
Correct |
1277 ms |
88036 KB |
Output is correct |
97 |
Correct |
1264 ms |
82100 KB |
Output is correct |
98 |
Correct |
959 ms |
88312 KB |
Output is correct |
99 |
Correct |
931 ms |
81656 KB |
Output is correct |
100 |
Correct |
1078 ms |
20856 KB |
Output is correct |
101 |
Correct |
1063 ms |
20888 KB |
Output is correct |
102 |
Correct |
1093 ms |
19832 KB |
Output is correct |
103 |
Correct |
1074 ms |
19832 KB |
Output is correct |
104 |
Correct |
1042 ms |
19452 KB |
Output is correct |
105 |
Correct |
1030 ms |
19448 KB |
Output is correct |
106 |
Correct |
1114 ms |
106744 KB |
Output is correct |
107 |
Correct |
1123 ms |
102560 KB |
Output is correct |
108 |
Correct |
1442 ms |
107256 KB |
Output is correct |
109 |
Correct |
1471 ms |
102392 KB |
Output is correct |
110 |
Correct |
1082 ms |
107624 KB |
Output is correct |
111 |
Correct |
1049 ms |
102852 KB |
Output is correct |
112 |
Correct |
1041 ms |
20728 KB |
Output is correct |
113 |
Correct |
1030 ms |
20856 KB |
Output is correct |
114 |
Correct |
1063 ms |
19740 KB |
Output is correct |
115 |
Correct |
1067 ms |
19780 KB |
Output is correct |
116 |
Correct |
1014 ms |
19436 KB |
Output is correct |
117 |
Correct |
1018 ms |
19400 KB |
Output is correct |
118 |
Correct |
1167 ms |
125924 KB |
Output is correct |
119 |
Correct |
1075 ms |
106652 KB |
Output is correct |
120 |
Correct |
1059 ms |
101668 KB |
Output is correct |
121 |
Correct |
1165 ms |
125860 KB |
Output is correct |
122 |
Correct |
1071 ms |
106232 KB |
Output is correct |
123 |
Correct |
1072 ms |
101496 KB |
Output is correct |
124 |
Correct |
1166 ms |
125688 KB |
Output is correct |
125 |
Correct |
1069 ms |
106744 KB |
Output is correct |
126 |
Correct |
1065 ms |
101504 KB |
Output is correct |