# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
311920 | 2020-10-12T02:44:23 Z | arnold518 | Bitaro’s Party (JOI18_bitaro) | C++14 | 1823 ms | 176676 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const int SQ = 100; const int INF = 1e9; int N, M, Q; vector<int> adj[MAXN+10]; int ans[MAXN+10]; int dp[MAXN+10]; int val[MAXN+10]; struct Data { int T, P; vector<int> V; }; Data A[MAXN+10]; vector<int> P[MAXN+10]; vector<pii> dp2[MAXN+10]; bool chk[MAXN+10]; int main() { memset(ans, -1, sizeof(ans)); scanf("%d%d%d", &N, &M, &Q); for(int i=1; i<=M; i++) { int u, v; scanf("%d%d", &u, &v); adj[v].push_back(u); } for(int i=1; i<=Q; i++) { int a, b; scanf("%d%d", &a, &b); A[i].T=a; A[i].P=i; while(b--) { int t; scanf("%d", &t); A[i].V.push_back(t); } if(A[i].V.size()>=SQ) { for(int j=1; j<=N; j++) dp[j]=0; for(auto it : A[i].V) dp[it]=-INF; for(int j=1; j<=N; j++) for(auto nxt : adj[j]) dp[j]=max(dp[j], dp[nxt]+1); if(dp[A[i].T]>=0) ans[i]=dp[A[i].T]; } else P[A[i].T].push_back(i); } for(int now=1; now<=N; now++) { dp2[now].push_back({0, now}); vector<int> V; for(auto nxt : adj[now]) { for(auto it : dp2[nxt]) { val[it.second]=max(val[it.second], it.first+1); V.push_back(it.second); } } for(auto it : V) { if(chk[it]) continue; chk[it]=true; dp2[now].push_back({val[it], it}); } for(auto it : V) chk[it]=false; sort(dp2[now].begin(), dp2[now].end(), greater<pii>()); while(dp2[now].size()>SQ) dp2[now].pop_back(); for(auto it : V) val[it]=0; for(auto it : dp2[now]) chk[it.second]=false; for(auto it : P[now]) { for(auto pt : A[it].V) chk[pt]=true; for(auto jt : dp2[now]) { if(!chk[jt.second]) { ans[it]=jt.first; break; } } for(auto pt : A[it].V) chk[pt]=false; } } for(int i=1; i<=Q; i++) printf("%d\n", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 21504 KB | Output is correct |
2 | Correct | 15 ms | 21504 KB | Output is correct |
3 | Correct | 17 ms | 21504 KB | Output is correct |
4 | Correct | 18 ms | 21504 KB | Output is correct |
5 | Correct | 19 ms | 22016 KB | Output is correct |
6 | Correct | 20 ms | 21904 KB | Output is correct |
7 | Correct | 19 ms | 21888 KB | Output is correct |
8 | Correct | 21 ms | 22528 KB | Output is correct |
9 | Correct | 21 ms | 22528 KB | Output is correct |
10 | Correct | 21 ms | 22528 KB | Output is correct |
11 | Correct | 21 ms | 22400 KB | Output is correct |
12 | Correct | 21 ms | 22400 KB | Output is correct |
13 | Correct | 21 ms | 22400 KB | Output is correct |
14 | Correct | 20 ms | 22144 KB | Output is correct |
15 | Correct | 20 ms | 22144 KB | Output is correct |
16 | Correct | 21 ms | 22144 KB | Output is correct |
17 | Correct | 21 ms | 22272 KB | Output is correct |
18 | Correct | 21 ms | 22144 KB | Output is correct |
19 | Correct | 21 ms | 22272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 21504 KB | Output is correct |
2 | Correct | 15 ms | 21504 KB | Output is correct |
3 | Correct | 17 ms | 21504 KB | Output is correct |
4 | Correct | 18 ms | 21504 KB | Output is correct |
5 | Correct | 19 ms | 22016 KB | Output is correct |
6 | Correct | 20 ms | 21904 KB | Output is correct |
7 | Correct | 19 ms | 21888 KB | Output is correct |
8 | Correct | 21 ms | 22528 KB | Output is correct |
9 | Correct | 21 ms | 22528 KB | Output is correct |
10 | Correct | 21 ms | 22528 KB | Output is correct |
11 | Correct | 21 ms | 22400 KB | Output is correct |
12 | Correct | 21 ms | 22400 KB | Output is correct |
13 | Correct | 21 ms | 22400 KB | Output is correct |
14 | Correct | 20 ms | 22144 KB | Output is correct |
15 | Correct | 20 ms | 22144 KB | Output is correct |
16 | Correct | 21 ms | 22144 KB | Output is correct |
17 | Correct | 21 ms | 22272 KB | Output is correct |
18 | Correct | 21 ms | 22144 KB | Output is correct |
19 | Correct | 21 ms | 22272 KB | Output is correct |
20 | Correct | 296 ms | 23888 KB | Output is correct |
21 | Correct | 303 ms | 24336 KB | Output is correct |
22 | Correct | 298 ms | 23840 KB | Output is correct |
23 | Correct | 318 ms | 24668 KB | Output is correct |
24 | Correct | 1020 ms | 137200 KB | Output is correct |
25 | Correct | 1022 ms | 134828 KB | Output is correct |
26 | Correct | 1016 ms | 134708 KB | Output is correct |
27 | Correct | 772 ms | 127232 KB | Output is correct |
28 | Correct | 773 ms | 127220 KB | Output is correct |
29 | Correct | 776 ms | 127092 KB | Output is correct |
30 | Correct | 774 ms | 127092 KB | Output is correct |
31 | Correct | 924 ms | 153844 KB | Output is correct |
32 | Correct | 764 ms | 126964 KB | Output is correct |
33 | Correct | 632 ms | 91768 KB | Output is correct |
34 | Correct | 830 ms | 122636 KB | Output is correct |
35 | Correct | 626 ms | 91384 KB | Output is correct |
36 | Correct | 718 ms | 108172 KB | Output is correct |
37 | Correct | 983 ms | 138976 KB | Output is correct |
38 | Correct | 709 ms | 108532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 21504 KB | Output is correct |
2 | Correct | 15 ms | 21504 KB | Output is correct |
3 | Correct | 17 ms | 21504 KB | Output is correct |
4 | Correct | 18 ms | 21504 KB | Output is correct |
5 | Correct | 19 ms | 22016 KB | Output is correct |
6 | Correct | 20 ms | 21904 KB | Output is correct |
7 | Correct | 19 ms | 21888 KB | Output is correct |
8 | Correct | 21 ms | 22528 KB | Output is correct |
9 | Correct | 21 ms | 22528 KB | Output is correct |
10 | Correct | 21 ms | 22528 KB | Output is correct |
11 | Correct | 21 ms | 22400 KB | Output is correct |
12 | Correct | 21 ms | 22400 KB | Output is correct |
13 | Correct | 21 ms | 22400 KB | Output is correct |
14 | Correct | 20 ms | 22144 KB | Output is correct |
15 | Correct | 20 ms | 22144 KB | Output is correct |
16 | Correct | 21 ms | 22144 KB | Output is correct |
17 | Correct | 21 ms | 22272 KB | Output is correct |
18 | Correct | 21 ms | 22144 KB | Output is correct |
19 | Correct | 21 ms | 22272 KB | Output is correct |
20 | Correct | 296 ms | 23888 KB | Output is correct |
21 | Correct | 303 ms | 24336 KB | Output is correct |
22 | Correct | 298 ms | 23840 KB | Output is correct |
23 | Correct | 318 ms | 24668 KB | Output is correct |
24 | Correct | 1020 ms | 137200 KB | Output is correct |
25 | Correct | 1022 ms | 134828 KB | Output is correct |
26 | Correct | 1016 ms | 134708 KB | Output is correct |
27 | Correct | 772 ms | 127232 KB | Output is correct |
28 | Correct | 773 ms | 127220 KB | Output is correct |
29 | Correct | 776 ms | 127092 KB | Output is correct |
30 | Correct | 774 ms | 127092 KB | Output is correct |
31 | Correct | 924 ms | 153844 KB | Output is correct |
32 | Correct | 764 ms | 126964 KB | Output is correct |
33 | Correct | 632 ms | 91768 KB | Output is correct |
34 | Correct | 830 ms | 122636 KB | Output is correct |
35 | Correct | 626 ms | 91384 KB | Output is correct |
36 | Correct | 718 ms | 108172 KB | Output is correct |
37 | Correct | 983 ms | 138976 KB | Output is correct |
38 | Correct | 709 ms | 108532 KB | Output is correct |
39 | Correct | 1144 ms | 142844 KB | Output is correct |
40 | Correct | 1038 ms | 136916 KB | Output is correct |
41 | Correct | 1823 ms | 137720 KB | Output is correct |
42 | Correct | 1195 ms | 136452 KB | Output is correct |
43 | Correct | 1046 ms | 138104 KB | Output is correct |
44 | Correct | 370 ms | 26564 KB | Output is correct |
45 | Correct | 321 ms | 26744 KB | Output is correct |
46 | Correct | 457 ms | 26304 KB | Output is correct |
47 | Correct | 332 ms | 25804 KB | Output is correct |
48 | Correct | 302 ms | 25672 KB | Output is correct |
49 | Correct | 865 ms | 134392 KB | Output is correct |
50 | Correct | 1491 ms | 130112 KB | Output is correct |
51 | Correct | 369 ms | 28864 KB | Output is correct |
52 | Correct | 457 ms | 26392 KB | Output is correct |
53 | Correct | 804 ms | 115088 KB | Output is correct |
54 | Correct | 1049 ms | 144728 KB | Output is correct |
55 | Correct | 1507 ms | 111096 KB | Output is correct |
56 | Correct | 1796 ms | 144552 KB | Output is correct |
57 | Correct | 375 ms | 29100 KB | Output is correct |
58 | Correct | 377 ms | 28852 KB | Output is correct |
59 | Correct | 456 ms | 26272 KB | Output is correct |
60 | Correct | 456 ms | 26360 KB | Output is correct |
61 | Correct | 926 ms | 130040 KB | Output is correct |
62 | Correct | 858 ms | 111480 KB | Output is correct |
63 | Correct | 1130 ms | 139640 KB | Output is correct |
64 | Correct | 1179 ms | 130188 KB | Output is correct |
65 | Correct | 1133 ms | 111228 KB | Output is correct |
66 | Correct | 1420 ms | 142584 KB | Output is correct |
67 | Correct | 1473 ms | 130040 KB | Output is correct |
68 | Correct | 1410 ms | 111480 KB | Output is correct |
69 | Correct | 1706 ms | 141816 KB | Output is correct |
70 | Correct | 784 ms | 130168 KB | Output is correct |
71 | Correct | 727 ms | 111224 KB | Output is correct |
72 | Correct | 977 ms | 142196 KB | Output is correct |
73 | Correct | 812 ms | 130040 KB | Output is correct |
74 | Correct | 751 ms | 111224 KB | Output is correct |
75 | Correct | 1012 ms | 143604 KB | Output is correct |
76 | Correct | 867 ms | 134552 KB | Output is correct |
77 | Correct | 1475 ms | 130580 KB | Output is correct |
78 | Correct | 784 ms | 130336 KB | Output is correct |
79 | Correct | 373 ms | 28820 KB | Output is correct |
80 | Correct | 454 ms | 26404 KB | Output is correct |
81 | Correct | 297 ms | 25588 KB | Output is correct |
82 | Correct | 853 ms | 134332 KB | Output is correct |
83 | Correct | 1040 ms | 166356 KB | Output is correct |
84 | Correct | 1480 ms | 130468 KB | Output is correct |
85 | Correct | 1711 ms | 176676 KB | Output is correct |
86 | Correct | 791 ms | 130296 KB | Output is correct |
87 | Correct | 983 ms | 162296 KB | Output is correct |
88 | Correct | 367 ms | 28844 KB | Output is correct |
89 | Correct | 370 ms | 28772 KB | Output is correct |
90 | Correct | 461 ms | 26292 KB | Output is correct |
91 | Correct | 462 ms | 26580 KB | Output is correct |
92 | Correct | 304 ms | 25408 KB | Output is correct |
93 | Correct | 301 ms | 25412 KB | Output is correct |
94 | Correct | 720 ms | 99192 KB | Output is correct |
95 | Correct | 958 ms | 136056 KB | Output is correct |
96 | Correct | 1303 ms | 95252 KB | Output is correct |
97 | Correct | 1606 ms | 133368 KB | Output is correct |
98 | Correct | 644 ms | 95188 KB | Output is correct |
99 | Correct | 875 ms | 129400 KB | Output is correct |
100 | Correct | 391 ms | 29060 KB | Output is correct |
101 | Correct | 397 ms | 29224 KB | Output is correct |
102 | Correct | 480 ms | 26600 KB | Output is correct |
103 | Correct | 474 ms | 26944 KB | Output is correct |
104 | Correct | 324 ms | 25804 KB | Output is correct |
105 | Correct | 321 ms | 25932 KB | Output is correct |
106 | Correct | 809 ms | 115448 KB | Output is correct |
107 | Correct | 1073 ms | 150868 KB | Output is correct |
108 | Correct | 1458 ms | 112000 KB | Output is correct |
109 | Correct | 1721 ms | 136956 KB | Output is correct |
110 | Correct | 749 ms | 111736 KB | Output is correct |
111 | Correct | 999 ms | 143984 KB | Output is correct |
112 | Correct | 373 ms | 29032 KB | Output is correct |
113 | Correct | 371 ms | 28840 KB | Output is correct |
114 | Correct | 456 ms | 26632 KB | Output is correct |
115 | Correct | 456 ms | 26516 KB | Output is correct |
116 | Correct | 291 ms | 25404 KB | Output is correct |
117 | Correct | 301 ms | 25520 KB | Output is correct |
118 | Correct | 762 ms | 129912 KB | Output is correct |
119 | Correct | 726 ms | 111480 KB | Output is correct |
120 | Correct | 1012 ms | 147424 KB | Output is correct |
121 | Correct | 775 ms | 130092 KB | Output is correct |
122 | Correct | 724 ms | 111224 KB | Output is correct |
123 | Correct | 1000 ms | 146636 KB | Output is correct |
124 | Correct | 761 ms | 129588 KB | Output is correct |
125 | Correct | 719 ms | 111480 KB | Output is correct |
126 | Correct | 966 ms | 142712 KB | Output is correct |