#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream& os, vector<A>& a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream& os, vector<A>& a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream& os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
template<typename A> istream& operator >>(istream& os,complex<A>& a){pair<A,A>aux;os>>aux;a=complex<A>(aux.first,aux.second);return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
#define x real
#define y imag
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using point=complex<double>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
void solve()
{
int n,m,q;
cin>>n>>m>>q;
const int sq=150;//int(sqrt(n));
vector<vector<int>>g(n);
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
g[y-1].pb(x-1);
}
vector<vector<pii>>best(n);
vector<int>val(n,-1);
//(m+n) * sq *log(sq*(m+n))
for(int i=0;i<n;i++)
{
vector<int>aux;
aux.pb(i);
val[i]=0;
for(auto &v:g[i])
{
for(auto &c:best[v])
{
aux.pb(c.first);
val[c.first]=max(val[c.first],c.second+1);
}
}
sort(all(aux));
aux.erase(unique(all(aux)),aux.end());
sort(all(aux),[&](int x,int y){
return val[x]>val[y];
});
for(auto &c:aux)
{
if(best[i].size()<sq)
best[i].pb({c,val[c]});
val[c]=-1;
}
}
vector<bool>viz(n,0);
while(q--)
{
int x,cnt;
cin>>x>>cnt;
x--;
vector<int>a(cnt);
cin>>a;
for(auto &c:a)
c--;
for(auto &c:a)
viz[c]=true;
int rez=-1;
if(cnt<sq)
{
for(auto &c:best[x])
{
if(!viz[c.first])
rez=max(rez,c.second);
}
}
else
{
vector<int>dp(x+1,-inf);
for(int i=0;i<=x;i++)
{
if(!viz[i])
dp[i]=0;
for(auto &c:g[i])
{
dp[i]=max(dp[i],dp[c]+1);
}
}
rez=max(dp[x],-1);
}
cout<<rez<<'\n';
for(auto &c:a)
viz[c]=false;
}
}
main()
{
i32 tt=1;
ios::sync_with_stdio(false);
cin.tie(0);
//cin>>tt;
while(tt--)
{
solve();
}
}
Compilation message
bitaro.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
128 | main()
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
8 ms |
2288 KB |
Output is correct |
9 |
Correct |
8 ms |
2264 KB |
Output is correct |
10 |
Correct |
8 ms |
2140 KB |
Output is correct |
11 |
Correct |
10 ms |
2140 KB |
Output is correct |
12 |
Correct |
8 ms |
1600 KB |
Output is correct |
13 |
Correct |
11 ms |
2164 KB |
Output is correct |
14 |
Correct |
8 ms |
1372 KB |
Output is correct |
15 |
Correct |
7 ms |
1112 KB |
Output is correct |
16 |
Correct |
7 ms |
1368 KB |
Output is correct |
17 |
Correct |
8 ms |
1624 KB |
Output is correct |
18 |
Correct |
7 ms |
1400 KB |
Output is correct |
19 |
Correct |
8 ms |
1716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
8 ms |
2288 KB |
Output is correct |
9 |
Correct |
8 ms |
2264 KB |
Output is correct |
10 |
Correct |
8 ms |
2140 KB |
Output is correct |
11 |
Correct |
10 ms |
2140 KB |
Output is correct |
12 |
Correct |
8 ms |
1600 KB |
Output is correct |
13 |
Correct |
11 ms |
2164 KB |
Output is correct |
14 |
Correct |
8 ms |
1372 KB |
Output is correct |
15 |
Correct |
7 ms |
1112 KB |
Output is correct |
16 |
Correct |
7 ms |
1368 KB |
Output is correct |
17 |
Correct |
8 ms |
1624 KB |
Output is correct |
18 |
Correct |
7 ms |
1400 KB |
Output is correct |
19 |
Correct |
8 ms |
1716 KB |
Output is correct |
20 |
Correct |
719 ms |
4008 KB |
Output is correct |
21 |
Correct |
714 ms |
3896 KB |
Output is correct |
22 |
Correct |
722 ms |
3936 KB |
Output is correct |
23 |
Correct |
914 ms |
4316 KB |
Output is correct |
24 |
Correct |
1237 ms |
154508 KB |
Output is correct |
25 |
Correct |
1244 ms |
159180 KB |
Output is correct |
26 |
Correct |
1260 ms |
159200 KB |
Output is correct |
27 |
Correct |
792 ms |
213744 KB |
Output is correct |
28 |
Correct |
790 ms |
213308 KB |
Output is correct |
29 |
Correct |
796 ms |
213796 KB |
Output is correct |
30 |
Correct |
917 ms |
213500 KB |
Output is correct |
31 |
Correct |
1554 ms |
208176 KB |
Output is correct |
32 |
Correct |
883 ms |
213084 KB |
Output is correct |
33 |
Correct |
887 ms |
135240 KB |
Output is correct |
34 |
Correct |
1008 ms |
117000 KB |
Output is correct |
35 |
Correct |
826 ms |
134548 KB |
Output is correct |
36 |
Correct |
990 ms |
174648 KB |
Output is correct |
37 |
Correct |
1288 ms |
162440 KB |
Output is correct |
38 |
Correct |
979 ms |
174820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
8 ms |
2288 KB |
Output is correct |
9 |
Correct |
8 ms |
2264 KB |
Output is correct |
10 |
Correct |
8 ms |
2140 KB |
Output is correct |
11 |
Correct |
10 ms |
2140 KB |
Output is correct |
12 |
Correct |
8 ms |
1600 KB |
Output is correct |
13 |
Correct |
11 ms |
2164 KB |
Output is correct |
14 |
Correct |
8 ms |
1372 KB |
Output is correct |
15 |
Correct |
7 ms |
1112 KB |
Output is correct |
16 |
Correct |
7 ms |
1368 KB |
Output is correct |
17 |
Correct |
8 ms |
1624 KB |
Output is correct |
18 |
Correct |
7 ms |
1400 KB |
Output is correct |
19 |
Correct |
8 ms |
1716 KB |
Output is correct |
20 |
Correct |
719 ms |
4008 KB |
Output is correct |
21 |
Correct |
714 ms |
3896 KB |
Output is correct |
22 |
Correct |
722 ms |
3936 KB |
Output is correct |
23 |
Correct |
914 ms |
4316 KB |
Output is correct |
24 |
Correct |
1237 ms |
154508 KB |
Output is correct |
25 |
Correct |
1244 ms |
159180 KB |
Output is correct |
26 |
Correct |
1260 ms |
159200 KB |
Output is correct |
27 |
Correct |
792 ms |
213744 KB |
Output is correct |
28 |
Correct |
790 ms |
213308 KB |
Output is correct |
29 |
Correct |
796 ms |
213796 KB |
Output is correct |
30 |
Correct |
917 ms |
213500 KB |
Output is correct |
31 |
Correct |
1554 ms |
208176 KB |
Output is correct |
32 |
Correct |
883 ms |
213084 KB |
Output is correct |
33 |
Correct |
887 ms |
135240 KB |
Output is correct |
34 |
Correct |
1008 ms |
117000 KB |
Output is correct |
35 |
Correct |
826 ms |
134548 KB |
Output is correct |
36 |
Correct |
990 ms |
174648 KB |
Output is correct |
37 |
Correct |
1288 ms |
162440 KB |
Output is correct |
38 |
Correct |
979 ms |
174820 KB |
Output is correct |
39 |
Correct |
1253 ms |
156560 KB |
Output is correct |
40 |
Correct |
1222 ms |
157600 KB |
Output is correct |
41 |
Correct |
1250 ms |
157780 KB |
Output is correct |
42 |
Correct |
1314 ms |
157604 KB |
Output is correct |
43 |
Correct |
1234 ms |
156752 KB |
Output is correct |
44 |
Correct |
779 ms |
6364 KB |
Output is correct |
45 |
Correct |
741 ms |
5704 KB |
Output is correct |
46 |
Correct |
731 ms |
5568 KB |
Output is correct |
47 |
Correct |
786 ms |
5588 KB |
Output is correct |
48 |
Correct |
720 ms |
5472 KB |
Output is correct |
49 |
Correct |
914 ms |
214236 KB |
Output is correct |
50 |
Correct |
812 ms |
213056 KB |
Output is correct |
51 |
Correct |
780 ms |
6060 KB |
Output is correct |
52 |
Correct |
738 ms |
5576 KB |
Output is correct |
53 |
Correct |
1055 ms |
174592 KB |
Output is correct |
54 |
Correct |
1392 ms |
162828 KB |
Output is correct |
55 |
Correct |
972 ms |
173676 KB |
Output is correct |
56 |
Correct |
1287 ms |
162768 KB |
Output is correct |
57 |
Correct |
774 ms |
6284 KB |
Output is correct |
58 |
Correct |
759 ms |
6084 KB |
Output is correct |
59 |
Correct |
731 ms |
5752 KB |
Output is correct |
60 |
Correct |
746 ms |
5712 KB |
Output is correct |
61 |
Correct |
885 ms |
213592 KB |
Output is correct |
62 |
Correct |
1069 ms |
174952 KB |
Output is correct |
63 |
Correct |
1310 ms |
161772 KB |
Output is correct |
64 |
Correct |
964 ms |
213656 KB |
Output is correct |
65 |
Correct |
1154 ms |
174080 KB |
Output is correct |
66 |
Correct |
1490 ms |
162960 KB |
Output is correct |
67 |
Correct |
1051 ms |
213600 KB |
Output is correct |
68 |
Correct |
1213 ms |
174840 KB |
Output is correct |
69 |
Correct |
1563 ms |
161056 KB |
Output is correct |
70 |
Correct |
1010 ms |
213592 KB |
Output is correct |
71 |
Correct |
1004 ms |
174940 KB |
Output is correct |
72 |
Correct |
1342 ms |
162644 KB |
Output is correct |
73 |
Correct |
858 ms |
213512 KB |
Output is correct |
74 |
Correct |
1000 ms |
174936 KB |
Output is correct |
75 |
Correct |
1263 ms |
162612 KB |
Output is correct |
76 |
Correct |
908 ms |
214676 KB |
Output is correct |
77 |
Correct |
992 ms |
213724 KB |
Output is correct |
78 |
Correct |
801 ms |
213896 KB |
Output is correct |
79 |
Correct |
758 ms |
6308 KB |
Output is correct |
80 |
Correct |
744 ms |
5828 KB |
Output is correct |
81 |
Correct |
710 ms |
5388 KB |
Output is correct |
82 |
Correct |
1004 ms |
214760 KB |
Output is correct |
83 |
Correct |
1699 ms |
209104 KB |
Output is correct |
84 |
Correct |
985 ms |
213492 KB |
Output is correct |
85 |
Correct |
1735 ms |
208332 KB |
Output is correct |
86 |
Correct |
889 ms |
213592 KB |
Output is correct |
87 |
Correct |
1574 ms |
208676 KB |
Output is correct |
88 |
Correct |
773 ms |
6460 KB |
Output is correct |
89 |
Correct |
761 ms |
6604 KB |
Output is correct |
90 |
Correct |
780 ms |
5864 KB |
Output is correct |
91 |
Correct |
771 ms |
5624 KB |
Output is correct |
92 |
Correct |
726 ms |
5476 KB |
Output is correct |
93 |
Correct |
722 ms |
5416 KB |
Output is correct |
94 |
Correct |
936 ms |
136604 KB |
Output is correct |
95 |
Correct |
1114 ms |
117512 KB |
Output is correct |
96 |
Correct |
949 ms |
134968 KB |
Output is correct |
97 |
Correct |
1220 ms |
118540 KB |
Output is correct |
98 |
Correct |
882 ms |
135420 KB |
Output is correct |
99 |
Correct |
1074 ms |
118032 KB |
Output is correct |
100 |
Correct |
892 ms |
6376 KB |
Output is correct |
101 |
Correct |
942 ms |
6428 KB |
Output is correct |
102 |
Correct |
875 ms |
6172 KB |
Output is correct |
103 |
Correct |
937 ms |
6156 KB |
Output is correct |
104 |
Correct |
857 ms |
5852 KB |
Output is correct |
105 |
Correct |
880 ms |
5876 KB |
Output is correct |
106 |
Correct |
1014 ms |
175036 KB |
Output is correct |
107 |
Correct |
1353 ms |
163488 KB |
Output is correct |
108 |
Correct |
1111 ms |
175196 KB |
Output is correct |
109 |
Correct |
1404 ms |
162256 KB |
Output is correct |
110 |
Correct |
1070 ms |
175824 KB |
Output is correct |
111 |
Correct |
1375 ms |
162856 KB |
Output is correct |
112 |
Correct |
804 ms |
6320 KB |
Output is correct |
113 |
Correct |
812 ms |
6280 KB |
Output is correct |
114 |
Correct |
791 ms |
5540 KB |
Output is correct |
115 |
Correct |
774 ms |
5888 KB |
Output is correct |
116 |
Correct |
791 ms |
5404 KB |
Output is correct |
117 |
Correct |
742 ms |
5756 KB |
Output is correct |
118 |
Correct |
833 ms |
213072 KB |
Output is correct |
119 |
Correct |
977 ms |
174500 KB |
Output is correct |
120 |
Correct |
1311 ms |
161996 KB |
Output is correct |
121 |
Correct |
865 ms |
213112 KB |
Output is correct |
122 |
Correct |
966 ms |
173936 KB |
Output is correct |
123 |
Correct |
1257 ms |
161696 KB |
Output is correct |
124 |
Correct |
825 ms |
213364 KB |
Output is correct |
125 |
Correct |
1027 ms |
174836 KB |
Output is correct |
126 |
Correct |
1259 ms |
161396 KB |
Output is correct |