#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
void GG(){cout<<"-1\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b) % mo;
}
const int maxn = 1e5+5;
const int BS = 305;
vector<int> tome[maxn];
vector<pii> far[maxn]; // The BS-th farthest nodes from i , {a,b}: farthest distance, node number
bool seen[maxn]; // Temporary array for things in far[i]
int farth[maxn];
signed main(){
IOS();
#ifdef BALBIT
freopen("input.in","r",stdin);
#endif // BALBIT
int n, m, q; cin>>n>>m>>q;
REP(i,m) {
int a, b; cin>>a>>b; tome[b-1].pb(a-1);
}
REP(i,n) {
far[i] = {{-1,i}};
for (int v : tome[i]) {
vector<pii> tmp = far[i]; far[i].clear();
int it = 0;
for (pii x : far[v]) {
while (it != SZ(tmp) && tmp[it].f>= x.f) {
if (!seen[tmp[it].s]) {
seen[tmp[it].s]=1;
far[i].push_back(tmp[it]);
}
++it;
}
if (!seen[x.s]) {
seen[x.s]=1; far[i].push_back(x);
}
}
FOR(j,it,SZ(tmp)) if (!seen[tmp[j].s]) {
far[i].pb(tmp[j]);
seen[tmp[j].s]=1;
}
for (pii x : far[i]) seen[x.s]=0;
while (far[i].size() > BS) far[i].pop_back();
}
for (pii &x : far[i]) {
++x.f;
}
// Make sure to set seen back to 0
}
while (q--) {
int v; cin>>v; --v;
int Y; cin>>Y;
vector<int> vec(Y);
REP(i,Y) {
cin>>vec[i]; seen[--vec[i]] = 1;
}
if (Y < BS) {
bool done = 0;
for (pii &x : far[v]) {
if (!seen[x.s]) {
cout<<x.f<<endl; done = 1; break;
}
}
if (!done) cout<<-1<<endl;
}else{
REP(i,n) {
farth[i] = seen[i]?-n-n:0;
for (int u : tome[i]) {
MX(farth[i], farth[u]+1);
}
}
cout<<max(farth[v],-1)<<endl;
}
REP(i,Y) {
seen[vec[i]] = 0;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
5624 KB |
Output is correct |
6 |
Correct |
9 ms |
5624 KB |
Output is correct |
7 |
Correct |
9 ms |
5496 KB |
Output is correct |
8 |
Correct |
17 ms |
8440 KB |
Output is correct |
9 |
Correct |
17 ms |
8440 KB |
Output is correct |
10 |
Correct |
17 ms |
8440 KB |
Output is correct |
11 |
Correct |
17 ms |
8028 KB |
Output is correct |
12 |
Correct |
11 ms |
6392 KB |
Output is correct |
13 |
Correct |
16 ms |
7800 KB |
Output is correct |
14 |
Correct |
14 ms |
7032 KB |
Output is correct |
15 |
Correct |
11 ms |
6008 KB |
Output is correct |
16 |
Correct |
14 ms |
7032 KB |
Output is correct |
17 |
Correct |
15 ms |
7288 KB |
Output is correct |
18 |
Correct |
12 ms |
6264 KB |
Output is correct |
19 |
Correct |
15 ms |
7288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
5624 KB |
Output is correct |
6 |
Correct |
9 ms |
5624 KB |
Output is correct |
7 |
Correct |
9 ms |
5496 KB |
Output is correct |
8 |
Correct |
17 ms |
8440 KB |
Output is correct |
9 |
Correct |
17 ms |
8440 KB |
Output is correct |
10 |
Correct |
17 ms |
8440 KB |
Output is correct |
11 |
Correct |
17 ms |
8028 KB |
Output is correct |
12 |
Correct |
11 ms |
6392 KB |
Output is correct |
13 |
Correct |
16 ms |
7800 KB |
Output is correct |
14 |
Correct |
14 ms |
7032 KB |
Output is correct |
15 |
Correct |
11 ms |
6008 KB |
Output is correct |
16 |
Correct |
14 ms |
7032 KB |
Output is correct |
17 |
Correct |
15 ms |
7288 KB |
Output is correct |
18 |
Correct |
12 ms |
6264 KB |
Output is correct |
19 |
Correct |
15 ms |
7288 KB |
Output is correct |
20 |
Correct |
606 ms |
11056 KB |
Output is correct |
21 |
Correct |
563 ms |
11092 KB |
Output is correct |
22 |
Correct |
617 ms |
11104 KB |
Output is correct |
23 |
Correct |
646 ms |
11156 KB |
Output is correct |
24 |
Correct |
1029 ms |
254256 KB |
Output is correct |
25 |
Correct |
1069 ms |
265748 KB |
Output is correct |
26 |
Correct |
1051 ms |
264824 KB |
Output is correct |
27 |
Correct |
1238 ms |
413328 KB |
Output is correct |
28 |
Correct |
1189 ms |
413276 KB |
Output is correct |
29 |
Correct |
1203 ms |
413336 KB |
Output is correct |
30 |
Correct |
1179 ms |
412992 KB |
Output is correct |
31 |
Correct |
1231 ms |
398328 KB |
Output is correct |
32 |
Correct |
1177 ms |
412996 KB |
Output is correct |
33 |
Correct |
874 ms |
255460 KB |
Output is correct |
34 |
Correct |
897 ms |
265260 KB |
Output is correct |
35 |
Correct |
871 ms |
253420 KB |
Output is correct |
36 |
Correct |
1048 ms |
334048 KB |
Output is correct |
37 |
Correct |
1048 ms |
302348 KB |
Output is correct |
38 |
Correct |
1037 ms |
335092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
5624 KB |
Output is correct |
6 |
Correct |
9 ms |
5624 KB |
Output is correct |
7 |
Correct |
9 ms |
5496 KB |
Output is correct |
8 |
Correct |
17 ms |
8440 KB |
Output is correct |
9 |
Correct |
17 ms |
8440 KB |
Output is correct |
10 |
Correct |
17 ms |
8440 KB |
Output is correct |
11 |
Correct |
17 ms |
8028 KB |
Output is correct |
12 |
Correct |
11 ms |
6392 KB |
Output is correct |
13 |
Correct |
16 ms |
7800 KB |
Output is correct |
14 |
Correct |
14 ms |
7032 KB |
Output is correct |
15 |
Correct |
11 ms |
6008 KB |
Output is correct |
16 |
Correct |
14 ms |
7032 KB |
Output is correct |
17 |
Correct |
15 ms |
7288 KB |
Output is correct |
18 |
Correct |
12 ms |
6264 KB |
Output is correct |
19 |
Correct |
15 ms |
7288 KB |
Output is correct |
20 |
Correct |
606 ms |
11056 KB |
Output is correct |
21 |
Correct |
563 ms |
11092 KB |
Output is correct |
22 |
Correct |
617 ms |
11104 KB |
Output is correct |
23 |
Correct |
646 ms |
11156 KB |
Output is correct |
24 |
Correct |
1029 ms |
254256 KB |
Output is correct |
25 |
Correct |
1069 ms |
265748 KB |
Output is correct |
26 |
Correct |
1051 ms |
264824 KB |
Output is correct |
27 |
Correct |
1238 ms |
413328 KB |
Output is correct |
28 |
Correct |
1189 ms |
413276 KB |
Output is correct |
29 |
Correct |
1203 ms |
413336 KB |
Output is correct |
30 |
Correct |
1179 ms |
412992 KB |
Output is correct |
31 |
Correct |
1231 ms |
398328 KB |
Output is correct |
32 |
Correct |
1177 ms |
412996 KB |
Output is correct |
33 |
Correct |
874 ms |
255460 KB |
Output is correct |
34 |
Correct |
897 ms |
265260 KB |
Output is correct |
35 |
Correct |
871 ms |
253420 KB |
Output is correct |
36 |
Correct |
1048 ms |
334048 KB |
Output is correct |
37 |
Correct |
1048 ms |
302348 KB |
Output is correct |
38 |
Correct |
1037 ms |
335092 KB |
Output is correct |
39 |
Correct |
1195 ms |
258168 KB |
Output is correct |
40 |
Correct |
1167 ms |
259836 KB |
Output is correct |
41 |
Correct |
1184 ms |
262400 KB |
Output is correct |
42 |
Correct |
1298 ms |
260664 KB |
Output is correct |
43 |
Correct |
1170 ms |
260192 KB |
Output is correct |
44 |
Correct |
642 ms |
12504 KB |
Output is correct |
45 |
Correct |
614 ms |
11628 KB |
Output is correct |
46 |
Correct |
611 ms |
11640 KB |
Output is correct |
47 |
Correct |
626 ms |
11196 KB |
Output is correct |
48 |
Correct |
604 ms |
11132 KB |
Output is correct |
49 |
Correct |
1450 ms |
414072 KB |
Output is correct |
50 |
Correct |
1403 ms |
412792 KB |
Output is correct |
51 |
Correct |
596 ms |
12280 KB |
Output is correct |
52 |
Correct |
571 ms |
11280 KB |
Output is correct |
53 |
Correct |
1258 ms |
333176 KB |
Output is correct |
54 |
Correct |
1259 ms |
303092 KB |
Output is correct |
55 |
Correct |
1211 ms |
332688 KB |
Output is correct |
56 |
Correct |
1217 ms |
303052 KB |
Output is correct |
57 |
Correct |
634 ms |
12240 KB |
Output is correct |
58 |
Correct |
646 ms |
12280 KB |
Output is correct |
59 |
Correct |
597 ms |
11508 KB |
Output is correct |
60 |
Correct |
607 ms |
11384 KB |
Output is correct |
61 |
Correct |
1514 ms |
413284 KB |
Output is correct |
62 |
Correct |
1333 ms |
334328 KB |
Output is correct |
63 |
Correct |
1333 ms |
301828 KB |
Output is correct |
64 |
Correct |
1746 ms |
413176 KB |
Output is correct |
65 |
Correct |
1555 ms |
332920 KB |
Output is correct |
66 |
Correct |
1587 ms |
303608 KB |
Output is correct |
67 |
Correct |
1395 ms |
412792 KB |
Output is correct |
68 |
Correct |
1207 ms |
333944 KB |
Output is correct |
69 |
Correct |
1189 ms |
299236 KB |
Output is correct |
70 |
Correct |
1417 ms |
413432 KB |
Output is correct |
71 |
Correct |
1254 ms |
334504 KB |
Output is correct |
72 |
Correct |
1246 ms |
303204 KB |
Output is correct |
73 |
Correct |
1441 ms |
413184 KB |
Output is correct |
74 |
Correct |
1251 ms |
334328 KB |
Output is correct |
75 |
Correct |
1240 ms |
303332 KB |
Output is correct |
76 |
Correct |
1484 ms |
414328 KB |
Output is correct |
77 |
Correct |
1398 ms |
412920 KB |
Output is correct |
78 |
Correct |
1415 ms |
413316 KB |
Output is correct |
79 |
Correct |
602 ms |
12536 KB |
Output is correct |
80 |
Correct |
572 ms |
11512 KB |
Output is correct |
81 |
Correct |
561 ms |
11088 KB |
Output is correct |
82 |
Correct |
1460 ms |
413816 KB |
Output is correct |
83 |
Correct |
1513 ms |
399512 KB |
Output is correct |
84 |
Correct |
1412 ms |
412472 KB |
Output is correct |
85 |
Correct |
1498 ms |
397800 KB |
Output is correct |
86 |
Correct |
1423 ms |
412920 KB |
Output is correct |
87 |
Correct |
1483 ms |
399140 KB |
Output is correct |
88 |
Correct |
645 ms |
12408 KB |
Output is correct |
89 |
Correct |
638 ms |
12408 KB |
Output is correct |
90 |
Correct |
606 ms |
11424 KB |
Output is correct |
91 |
Correct |
626 ms |
11688 KB |
Output is correct |
92 |
Correct |
606 ms |
11000 KB |
Output is correct |
93 |
Correct |
599 ms |
11064 KB |
Output is correct |
94 |
Correct |
1060 ms |
256476 KB |
Output is correct |
95 |
Correct |
1060 ms |
272968 KB |
Output is correct |
96 |
Correct |
997 ms |
253760 KB |
Output is correct |
97 |
Correct |
1031 ms |
276216 KB |
Output is correct |
98 |
Correct |
1045 ms |
255080 KB |
Output is correct |
99 |
Correct |
1058 ms |
271356 KB |
Output is correct |
100 |
Correct |
701 ms |
12392 KB |
Output is correct |
101 |
Correct |
667 ms |
12456 KB |
Output is correct |
102 |
Correct |
662 ms |
11512 KB |
Output is correct |
103 |
Correct |
664 ms |
11588 KB |
Output is correct |
104 |
Correct |
671 ms |
11148 KB |
Output is correct |
105 |
Correct |
650 ms |
10996 KB |
Output is correct |
106 |
Correct |
1256 ms |
334140 KB |
Output is correct |
107 |
Correct |
1294 ms |
303736 KB |
Output is correct |
108 |
Correct |
1235 ms |
334896 KB |
Output is correct |
109 |
Correct |
1192 ms |
302200 KB |
Output is correct |
110 |
Correct |
1216 ms |
335540 KB |
Output is correct |
111 |
Correct |
1253 ms |
303832 KB |
Output is correct |
112 |
Correct |
640 ms |
12456 KB |
Output is correct |
113 |
Correct |
639 ms |
12536 KB |
Output is correct |
114 |
Correct |
604 ms |
11512 KB |
Output is correct |
115 |
Correct |
616 ms |
11388 KB |
Output is correct |
116 |
Correct |
599 ms |
11184 KB |
Output is correct |
117 |
Correct |
607 ms |
11256 KB |
Output is correct |
118 |
Correct |
1397 ms |
412696 KB |
Output is correct |
119 |
Correct |
1203 ms |
334712 KB |
Output is correct |
120 |
Correct |
1191 ms |
301944 KB |
Output is correct |
121 |
Correct |
1393 ms |
412932 KB |
Output is correct |
122 |
Correct |
1214 ms |
333284 KB |
Output is correct |
123 |
Correct |
1196 ms |
302200 KB |
Output is correct |
124 |
Correct |
1395 ms |
412768 KB |
Output is correct |
125 |
Correct |
1202 ms |
334968 KB |
Output is correct |
126 |
Correct |
1199 ms |
300920 KB |
Output is correct |