#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef vector<pair<int,int>> vii;
const int maxn = 1e5 + 20;
const int sq = 150;
vector<int> in[maxn];
vii path[maxn];
int dp[maxn] , mx[maxn] , all[maxn];
bool is[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n , m , q;
cin >> n >> m >> q;
for(int i = 0; i < m; i++)
{
int a , b;
cin >> a >> b;
a-- , b--;
in[b].pb(a);
}
memset(mx , -1 , sizeof mx);
for(int v = 0; v < n; v++)
{
int t = 0;
all[t++] = v , mx[v] = 0;
for(auto u : in[v])
for(auto w : path[u])
{
mx[w.second] = max(mx[w.second] , w.first + 1);
all[t++] = w.second;
}
for(int i = 0; i < t; i++)
if(mx[all[i]] != -1)
path[v].pb({mx[all[i]] , all[i]}) , mx[all[i]] = -1;
sort(path[v].begin() , path[v].end());
reverse(path[v].begin() , path[v].end());
while(path[v].size() > sq)
path[v].pop_back();
}
while(q--)
{
int v , sz;
cin >> v >> sz;
v--;
vector<int> tmp;
for(int _ = 0; _ < sz; _++)
{
int x;
cin >> x;
x--;
tmp.pb(x);
is[x] = 1;
}
if(sz >= sq)
{
for(int i = 0; i <= v; i++)
{
dp[i] = -1e9;
if(!is[i])
dp[i] = 0;
for(auto u : in[i])
dp[i] = max(dp[i] , dp[u] + 1);
}
dp[v] = max(dp[v] , -1);
cout << dp[v] << endl;
}
else
{
bool f = 0;
for(auto x : path[v])
if(!is[x.second])
{
cout << x.first << endl;
f = 1;
break;
}
if(!f)
cout << -1 << endl;
}
for(auto x : tmp)
is[x] = 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5496 KB |
Output is correct |
2 |
Correct |
6 ms |
5368 KB |
Output is correct |
3 |
Correct |
6 ms |
5368 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
8 ms |
5880 KB |
Output is correct |
8 |
Correct |
11 ms |
7288 KB |
Output is correct |
9 |
Correct |
11 ms |
7288 KB |
Output is correct |
10 |
Correct |
12 ms |
7288 KB |
Output is correct |
11 |
Correct |
12 ms |
7224 KB |
Output is correct |
12 |
Correct |
12 ms |
6520 KB |
Output is correct |
13 |
Correct |
11 ms |
7160 KB |
Output is correct |
14 |
Correct |
10 ms |
6520 KB |
Output is correct |
15 |
Correct |
10 ms |
6136 KB |
Output is correct |
16 |
Correct |
11 ms |
6524 KB |
Output is correct |
17 |
Correct |
11 ms |
6776 KB |
Output is correct |
18 |
Correct |
10 ms |
6392 KB |
Output is correct |
19 |
Correct |
11 ms |
6776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5496 KB |
Output is correct |
2 |
Correct |
6 ms |
5368 KB |
Output is correct |
3 |
Correct |
6 ms |
5368 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
8 ms |
5880 KB |
Output is correct |
8 |
Correct |
11 ms |
7288 KB |
Output is correct |
9 |
Correct |
11 ms |
7288 KB |
Output is correct |
10 |
Correct |
12 ms |
7288 KB |
Output is correct |
11 |
Correct |
12 ms |
7224 KB |
Output is correct |
12 |
Correct |
12 ms |
6520 KB |
Output is correct |
13 |
Correct |
11 ms |
7160 KB |
Output is correct |
14 |
Correct |
10 ms |
6520 KB |
Output is correct |
15 |
Correct |
10 ms |
6136 KB |
Output is correct |
16 |
Correct |
11 ms |
6524 KB |
Output is correct |
17 |
Correct |
11 ms |
6776 KB |
Output is correct |
18 |
Correct |
10 ms |
6392 KB |
Output is correct |
19 |
Correct |
11 ms |
6776 KB |
Output is correct |
20 |
Correct |
98 ms |
8696 KB |
Output is correct |
21 |
Correct |
105 ms |
8620 KB |
Output is correct |
22 |
Correct |
99 ms |
8596 KB |
Output is correct |
23 |
Correct |
108 ms |
8796 KB |
Output is correct |
24 |
Correct |
1088 ms |
156108 KB |
Output is correct |
25 |
Correct |
1044 ms |
157056 KB |
Output is correct |
26 |
Correct |
1014 ms |
157724 KB |
Output is correct |
27 |
Correct |
680 ms |
211152 KB |
Output is correct |
28 |
Correct |
694 ms |
211220 KB |
Output is correct |
29 |
Correct |
716 ms |
211108 KB |
Output is correct |
30 |
Correct |
813 ms |
211064 KB |
Output is correct |
31 |
Correct |
978 ms |
208376 KB |
Output is correct |
32 |
Correct |
796 ms |
210900 KB |
Output is correct |
33 |
Correct |
621 ms |
133060 KB |
Output is correct |
34 |
Correct |
904 ms |
154240 KB |
Output is correct |
35 |
Correct |
639 ms |
132220 KB |
Output is correct |
36 |
Correct |
676 ms |
172512 KB |
Output is correct |
37 |
Correct |
955 ms |
166440 KB |
Output is correct |
38 |
Correct |
645 ms |
172660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5496 KB |
Output is correct |
2 |
Correct |
6 ms |
5368 KB |
Output is correct |
3 |
Correct |
6 ms |
5368 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5880 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
8 ms |
5880 KB |
Output is correct |
8 |
Correct |
11 ms |
7288 KB |
Output is correct |
9 |
Correct |
11 ms |
7288 KB |
Output is correct |
10 |
Correct |
12 ms |
7288 KB |
Output is correct |
11 |
Correct |
12 ms |
7224 KB |
Output is correct |
12 |
Correct |
12 ms |
6520 KB |
Output is correct |
13 |
Correct |
11 ms |
7160 KB |
Output is correct |
14 |
Correct |
10 ms |
6520 KB |
Output is correct |
15 |
Correct |
10 ms |
6136 KB |
Output is correct |
16 |
Correct |
11 ms |
6524 KB |
Output is correct |
17 |
Correct |
11 ms |
6776 KB |
Output is correct |
18 |
Correct |
10 ms |
6392 KB |
Output is correct |
19 |
Correct |
11 ms |
6776 KB |
Output is correct |
20 |
Correct |
98 ms |
8696 KB |
Output is correct |
21 |
Correct |
105 ms |
8620 KB |
Output is correct |
22 |
Correct |
99 ms |
8596 KB |
Output is correct |
23 |
Correct |
108 ms |
8796 KB |
Output is correct |
24 |
Correct |
1088 ms |
156108 KB |
Output is correct |
25 |
Correct |
1044 ms |
157056 KB |
Output is correct |
26 |
Correct |
1014 ms |
157724 KB |
Output is correct |
27 |
Correct |
680 ms |
211152 KB |
Output is correct |
28 |
Correct |
694 ms |
211220 KB |
Output is correct |
29 |
Correct |
716 ms |
211108 KB |
Output is correct |
30 |
Correct |
813 ms |
211064 KB |
Output is correct |
31 |
Correct |
978 ms |
208376 KB |
Output is correct |
32 |
Correct |
796 ms |
210900 KB |
Output is correct |
33 |
Correct |
621 ms |
133060 KB |
Output is correct |
34 |
Correct |
904 ms |
154240 KB |
Output is correct |
35 |
Correct |
639 ms |
132220 KB |
Output is correct |
36 |
Correct |
676 ms |
172512 KB |
Output is correct |
37 |
Correct |
955 ms |
166440 KB |
Output is correct |
38 |
Correct |
645 ms |
172660 KB |
Output is correct |
39 |
Correct |
1331 ms |
156728 KB |
Output is correct |
40 |
Correct |
1180 ms |
155432 KB |
Output is correct |
41 |
Correct |
1203 ms |
156624 KB |
Output is correct |
42 |
Correct |
1214 ms |
156880 KB |
Output is correct |
43 |
Correct |
1144 ms |
157304 KB |
Output is correct |
44 |
Correct |
263 ms |
8952 KB |
Output is correct |
45 |
Correct |
130 ms |
8700 KB |
Output is correct |
46 |
Correct |
116 ms |
8552 KB |
Output is correct |
47 |
Correct |
116 ms |
8516 KB |
Output is correct |
48 |
Correct |
105 ms |
8736 KB |
Output is correct |
49 |
Correct |
999 ms |
211196 KB |
Output is correct |
50 |
Correct |
816 ms |
210548 KB |
Output is correct |
51 |
Correct |
268 ms |
8952 KB |
Output is correct |
52 |
Correct |
113 ms |
8700 KB |
Output is correct |
53 |
Correct |
971 ms |
171480 KB |
Output is correct |
54 |
Correct |
1198 ms |
164272 KB |
Output is correct |
55 |
Correct |
796 ms |
171740 KB |
Output is correct |
56 |
Correct |
1071 ms |
168652 KB |
Output is correct |
57 |
Correct |
259 ms |
9464 KB |
Output is correct |
58 |
Correct |
266 ms |
9596 KB |
Output is correct |
59 |
Correct |
112 ms |
9044 KB |
Output is correct |
60 |
Correct |
110 ms |
9236 KB |
Output is correct |
61 |
Correct |
780 ms |
211352 KB |
Output is correct |
62 |
Correct |
814 ms |
172664 KB |
Output is correct |
63 |
Correct |
1030 ms |
164656 KB |
Output is correct |
64 |
Correct |
976 ms |
211372 KB |
Output is correct |
65 |
Correct |
972 ms |
171980 KB |
Output is correct |
66 |
Correct |
1357 ms |
165608 KB |
Output is correct |
67 |
Correct |
1080 ms |
211560 KB |
Output is correct |
68 |
Correct |
1075 ms |
172856 KB |
Output is correct |
69 |
Correct |
1365 ms |
165264 KB |
Output is correct |
70 |
Correct |
814 ms |
211460 KB |
Output is correct |
71 |
Correct |
757 ms |
172536 KB |
Output is correct |
72 |
Correct |
1008 ms |
165240 KB |
Output is correct |
73 |
Correct |
836 ms |
211448 KB |
Output is correct |
74 |
Correct |
800 ms |
172688 KB |
Output is correct |
75 |
Correct |
1020 ms |
166944 KB |
Output is correct |
76 |
Correct |
895 ms |
211600 KB |
Output is correct |
77 |
Correct |
885 ms |
211620 KB |
Output is correct |
78 |
Correct |
725 ms |
211640 KB |
Output is correct |
79 |
Correct |
260 ms |
9548 KB |
Output is correct |
80 |
Correct |
144 ms |
9080 KB |
Output is correct |
81 |
Correct |
105 ms |
9004 KB |
Output is correct |
82 |
Correct |
993 ms |
211424 KB |
Output is correct |
83 |
Correct |
1351 ms |
208992 KB |
Output is correct |
84 |
Correct |
1145 ms |
211288 KB |
Output is correct |
85 |
Correct |
1199 ms |
210196 KB |
Output is correct |
86 |
Correct |
739 ms |
211540 KB |
Output is correct |
87 |
Correct |
956 ms |
209440 KB |
Output is correct |
88 |
Correct |
256 ms |
9568 KB |
Output is correct |
89 |
Correct |
261 ms |
9464 KB |
Output is correct |
90 |
Correct |
136 ms |
9192 KB |
Output is correct |
91 |
Correct |
131 ms |
9088 KB |
Output is correct |
92 |
Correct |
105 ms |
9148 KB |
Output is correct |
93 |
Correct |
109 ms |
9080 KB |
Output is correct |
94 |
Correct |
890 ms |
133672 KB |
Output is correct |
95 |
Correct |
1167 ms |
162788 KB |
Output is correct |
96 |
Correct |
878 ms |
133020 KB |
Output is correct |
97 |
Correct |
1225 ms |
164412 KB |
Output is correct |
98 |
Correct |
649 ms |
133544 KB |
Output is correct |
99 |
Correct |
974 ms |
159832 KB |
Output is correct |
100 |
Correct |
357 ms |
9616 KB |
Output is correct |
101 |
Incorrect |
268 ms |
9816 KB |
Output isn't correct |
102 |
Halted |
0 ms |
0 KB |
- |