#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 100005;
const int MAXM = 200005;
const int MAXQ = 100005;
const int SQRN = 335;
vector<int> G[MAXN];
pii V[MAXN][SQRN]; int Vn[MAXN];
int dp[MAXN];
int chk[MAXN], chkn;
vector<int> DV[MAXQ];
int C[MAXQ], D[MAXQ];
int A[MAXM], B[MAXM];
int N, M, Q;
int main() {
ios::sync_with_stdio(false);
cin >> N >> M >> Q;
for(int i = 1; i <= M; i++) cin >> A[i] >> B[i];
for(int i = 1; i <= Q; i++) {
cin >> C[i] >> D[i];
for(int j = 0, v; j < D[i]; j++) {
cin >> v;
DV[i].eb(v);
}
}
for(int i = 1; i <= M; i++) G[B[i]].eb(A[i]);
for(int i = 1; i <= N; i++) {
pii *V = ::V[i];
int &Vn = ::Vn[i];
chkn++;
priority_queue<pair<int, pii>> PQ;
for(int v : G[i]) PQ.push(pair<int, pii>(::V[v][0].second, pii(v, 0)));
for(int v, idx, p; !PQ.empty() && Vn < SQRN;) {
tie(v, idx) = PQ.top().second; PQ.pop();
p = ::V[v][idx].first;
if(chk[p] != chkn) {
chk[p] = chkn;
V[Vn] = ::V[v][idx]; Vn++;
}
for(idx++; idx < ::Vn[v] && chk[::V[v][idx].first] == chkn; idx++);
if(::Vn[v] == idx) continue;
PQ.push(pair<int, pii>(::V[v][idx].second, pii(v, idx)));
}
for(int j = 0; j < Vn; j++) V[j].second++;
if(Vn < SQRN) V[Vn++] = pii(i, 0);
}
for(int qi = 1; qi <= Q; qi++) {
chkn++; for(int v : DV[qi]) chk[v] = chkn;
if(D[qi] < SQRN) {
int ret = -1, idx = C[qi];
for(int i = 0; i < Vn[idx]; i++) {
if(chk[V[idx][i].first] != chkn) {
ret = V[idx][i].second;
break;
}
}
printf("%d\n", ret);
} else {
fill(dp, dp+N+1, 0);
dp[C[qi]] = 1;
int ret = -1;
for(int i = C[qi]; i; i--) {
if(!dp[i]) continue;
if(chk[i] != chkn) upmax(ret, dp[i] - 1);
for(int v : G[i])
upmax(dp[v], dp[i] + 1);
}
printf("%d\n", ret);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
3 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
7 ms |
7808 KB |
Output is correct |
7 |
Correct |
8 ms |
7808 KB |
Output is correct |
8 |
Correct |
16 ms |
7808 KB |
Output is correct |
9 |
Correct |
16 ms |
7808 KB |
Output is correct |
10 |
Correct |
16 ms |
7808 KB |
Output is correct |
11 |
Correct |
15 ms |
7840 KB |
Output is correct |
12 |
Correct |
10 ms |
7808 KB |
Output is correct |
13 |
Correct |
14 ms |
7808 KB |
Output is correct |
14 |
Correct |
13 ms |
7808 KB |
Output is correct |
15 |
Correct |
10 ms |
7808 KB |
Output is correct |
16 |
Correct |
13 ms |
7808 KB |
Output is correct |
17 |
Correct |
13 ms |
7808 KB |
Output is correct |
18 |
Correct |
10 ms |
7808 KB |
Output is correct |
19 |
Correct |
13 ms |
7808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
3 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
7 ms |
7808 KB |
Output is correct |
7 |
Correct |
8 ms |
7808 KB |
Output is correct |
8 |
Correct |
16 ms |
7808 KB |
Output is correct |
9 |
Correct |
16 ms |
7808 KB |
Output is correct |
10 |
Correct |
16 ms |
7808 KB |
Output is correct |
11 |
Correct |
15 ms |
7840 KB |
Output is correct |
12 |
Correct |
10 ms |
7808 KB |
Output is correct |
13 |
Correct |
14 ms |
7808 KB |
Output is correct |
14 |
Correct |
13 ms |
7808 KB |
Output is correct |
15 |
Correct |
10 ms |
7808 KB |
Output is correct |
16 |
Correct |
13 ms |
7808 KB |
Output is correct |
17 |
Correct |
13 ms |
7808 KB |
Output is correct |
18 |
Correct |
10 ms |
7808 KB |
Output is correct |
19 |
Correct |
13 ms |
7808 KB |
Output is correct |
20 |
Correct |
220 ms |
12024 KB |
Output is correct |
21 |
Correct |
173 ms |
12024 KB |
Output is correct |
22 |
Correct |
223 ms |
12024 KB |
Output is correct |
23 |
Correct |
149 ms |
12152 KB |
Output is correct |
24 |
Correct |
1129 ms |
275832 KB |
Output is correct |
25 |
Correct |
1158 ms |
275828 KB |
Output is correct |
26 |
Correct |
1149 ms |
275576 KB |
Output is correct |
27 |
Correct |
1416 ms |
276216 KB |
Output is correct |
28 |
Correct |
1433 ms |
276088 KB |
Output is correct |
29 |
Correct |
1410 ms |
275960 KB |
Output is correct |
30 |
Correct |
1439 ms |
276216 KB |
Output is correct |
31 |
Correct |
1413 ms |
276216 KB |
Output is correct |
32 |
Correct |
1422 ms |
275928 KB |
Output is correct |
33 |
Correct |
998 ms |
275704 KB |
Output is correct |
34 |
Correct |
924 ms |
275836 KB |
Output is correct |
35 |
Correct |
997 ms |
275832 KB |
Output is correct |
36 |
Correct |
1227 ms |
275960 KB |
Output is correct |
37 |
Correct |
1193 ms |
275584 KB |
Output is correct |
38 |
Correct |
1231 ms |
275576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
3 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
7936 KB |
Output is correct |
6 |
Correct |
7 ms |
7808 KB |
Output is correct |
7 |
Correct |
8 ms |
7808 KB |
Output is correct |
8 |
Correct |
16 ms |
7808 KB |
Output is correct |
9 |
Correct |
16 ms |
7808 KB |
Output is correct |
10 |
Correct |
16 ms |
7808 KB |
Output is correct |
11 |
Correct |
15 ms |
7840 KB |
Output is correct |
12 |
Correct |
10 ms |
7808 KB |
Output is correct |
13 |
Correct |
14 ms |
7808 KB |
Output is correct |
14 |
Correct |
13 ms |
7808 KB |
Output is correct |
15 |
Correct |
10 ms |
7808 KB |
Output is correct |
16 |
Correct |
13 ms |
7808 KB |
Output is correct |
17 |
Correct |
13 ms |
7808 KB |
Output is correct |
18 |
Correct |
10 ms |
7808 KB |
Output is correct |
19 |
Correct |
13 ms |
7808 KB |
Output is correct |
20 |
Correct |
220 ms |
12024 KB |
Output is correct |
21 |
Correct |
173 ms |
12024 KB |
Output is correct |
22 |
Correct |
223 ms |
12024 KB |
Output is correct |
23 |
Correct |
149 ms |
12152 KB |
Output is correct |
24 |
Correct |
1129 ms |
275832 KB |
Output is correct |
25 |
Correct |
1158 ms |
275828 KB |
Output is correct |
26 |
Correct |
1149 ms |
275576 KB |
Output is correct |
27 |
Correct |
1416 ms |
276216 KB |
Output is correct |
28 |
Correct |
1433 ms |
276088 KB |
Output is correct |
29 |
Correct |
1410 ms |
275960 KB |
Output is correct |
30 |
Correct |
1439 ms |
276216 KB |
Output is correct |
31 |
Correct |
1413 ms |
276216 KB |
Output is correct |
32 |
Correct |
1422 ms |
275928 KB |
Output is correct |
33 |
Correct |
998 ms |
275704 KB |
Output is correct |
34 |
Correct |
924 ms |
275836 KB |
Output is correct |
35 |
Correct |
997 ms |
275832 KB |
Output is correct |
36 |
Correct |
1227 ms |
275960 KB |
Output is correct |
37 |
Correct |
1193 ms |
275584 KB |
Output is correct |
38 |
Correct |
1231 ms |
275576 KB |
Output is correct |
39 |
Correct |
1180 ms |
279248 KB |
Output is correct |
40 |
Correct |
1152 ms |
276188 KB |
Output is correct |
41 |
Correct |
1168 ms |
275872 KB |
Output is correct |
42 |
Correct |
1176 ms |
276344 KB |
Output is correct |
43 |
Correct |
1195 ms |
276088 KB |
Output is correct |
44 |
Correct |
271 ms |
16104 KB |
Output is correct |
45 |
Correct |
245 ms |
13272 KB |
Output is correct |
46 |
Correct |
244 ms |
12920 KB |
Output is correct |
47 |
Correct |
257 ms |
12392 KB |
Output is correct |
48 |
Correct |
238 ms |
12004 KB |
Output is correct |
49 |
Correct |
1482 ms |
279220 KB |
Output is correct |
50 |
Correct |
1453 ms |
275584 KB |
Output is correct |
51 |
Correct |
217 ms |
15864 KB |
Output is correct |
52 |
Correct |
184 ms |
12920 KB |
Output is correct |
53 |
Correct |
1345 ms |
278904 KB |
Output is correct |
54 |
Correct |
1343 ms |
278720 KB |
Output is correct |
55 |
Correct |
1286 ms |
275656 KB |
Output is correct |
56 |
Correct |
1243 ms |
275496 KB |
Output is correct |
57 |
Correct |
272 ms |
16028 KB |
Output is correct |
58 |
Correct |
287 ms |
15864 KB |
Output is correct |
59 |
Correct |
235 ms |
12792 KB |
Output is correct |
60 |
Correct |
234 ms |
12848 KB |
Output is correct |
61 |
Correct |
1548 ms |
276100 KB |
Output is correct |
62 |
Correct |
1334 ms |
275976 KB |
Output is correct |
63 |
Correct |
1247 ms |
276104 KB |
Output is correct |
64 |
Correct |
1649 ms |
276096 KB |
Output is correct |
65 |
Correct |
1384 ms |
276224 KB |
Output is correct |
66 |
Correct |
1270 ms |
276124 KB |
Output is correct |
67 |
Correct |
1403 ms |
275704 KB |
Output is correct |
68 |
Correct |
1246 ms |
275552 KB |
Output is correct |
69 |
Correct |
1199 ms |
275536 KB |
Output is correct |
70 |
Correct |
1428 ms |
276200 KB |
Output is correct |
71 |
Correct |
1319 ms |
275992 KB |
Output is correct |
72 |
Correct |
1233 ms |
276020 KB |
Output is correct |
73 |
Correct |
1584 ms |
276268 KB |
Output is correct |
74 |
Correct |
1331 ms |
276124 KB |
Output is correct |
75 |
Correct |
1276 ms |
276020 KB |
Output is correct |
76 |
Correct |
1510 ms |
279632 KB |
Output is correct |
77 |
Correct |
1480 ms |
276508 KB |
Output is correct |
78 |
Correct |
1469 ms |
276544 KB |
Output is correct |
79 |
Correct |
239 ms |
15924 KB |
Output is correct |
80 |
Correct |
192 ms |
12920 KB |
Output is correct |
81 |
Correct |
250 ms |
12024 KB |
Output is correct |
82 |
Correct |
1506 ms |
279624 KB |
Output is correct |
83 |
Correct |
1477 ms |
279444 KB |
Output is correct |
84 |
Correct |
1462 ms |
276472 KB |
Output is correct |
85 |
Correct |
1417 ms |
276524 KB |
Output is correct |
86 |
Correct |
1455 ms |
276728 KB |
Output is correct |
87 |
Correct |
1466 ms |
276728 KB |
Output is correct |
88 |
Correct |
271 ms |
15992 KB |
Output is correct |
89 |
Correct |
271 ms |
15992 KB |
Output is correct |
90 |
Correct |
247 ms |
13048 KB |
Output is correct |
91 |
Correct |
228 ms |
12920 KB |
Output is correct |
92 |
Correct |
232 ms |
12060 KB |
Output is correct |
93 |
Correct |
244 ms |
12024 KB |
Output is correct |
94 |
Correct |
1081 ms |
279072 KB |
Output is correct |
95 |
Correct |
981 ms |
278904 KB |
Output is correct |
96 |
Correct |
1018 ms |
275832 KB |
Output is correct |
97 |
Correct |
975 ms |
275832 KB |
Output is correct |
98 |
Correct |
1034 ms |
276088 KB |
Output is correct |
99 |
Correct |
982 ms |
276112 KB |
Output is correct |
100 |
Correct |
211 ms |
16068 KB |
Output is correct |
101 |
Correct |
198 ms |
15900 KB |
Output is correct |
102 |
Correct |
162 ms |
13048 KB |
Output is correct |
103 |
Correct |
166 ms |
13324 KB |
Output is correct |
104 |
Correct |
155 ms |
12024 KB |
Output is correct |
105 |
Correct |
161 ms |
12024 KB |
Output is correct |
106 |
Correct |
1315 ms |
279384 KB |
Output is correct |
107 |
Correct |
1271 ms |
279008 KB |
Output is correct |
108 |
Correct |
1276 ms |
275960 KB |
Output is correct |
109 |
Correct |
1204 ms |
275960 KB |
Output is correct |
110 |
Correct |
1296 ms |
276088 KB |
Output is correct |
111 |
Correct |
1210 ms |
276188 KB |
Output is correct |
112 |
Correct |
261 ms |
15868 KB |
Output is correct |
113 |
Correct |
284 ms |
15992 KB |
Output is correct |
114 |
Correct |
235 ms |
13048 KB |
Output is correct |
115 |
Correct |
237 ms |
13176 KB |
Output is correct |
116 |
Correct |
232 ms |
12024 KB |
Output is correct |
117 |
Correct |
230 ms |
12024 KB |
Output is correct |
118 |
Correct |
1459 ms |
275832 KB |
Output is correct |
119 |
Correct |
1260 ms |
276008 KB |
Output is correct |
120 |
Correct |
1231 ms |
275956 KB |
Output is correct |
121 |
Correct |
1439 ms |
275960 KB |
Output is correct |
122 |
Correct |
1284 ms |
275960 KB |
Output is correct |
123 |
Correct |
1239 ms |
275828 KB |
Output is correct |
124 |
Correct |
1438 ms |
275840 KB |
Output is correct |
125 |
Correct |
1251 ms |
275728 KB |
Output is correct |
126 |
Correct |
1205 ms |
275576 KB |
Output is correct |