# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
535768 | 2022-03-11T07:01:07 Z | 79brue | Bitaro’s Party (JOI18_bitaro) | C++14 | 1499 ms | 220028 KB |
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define LIM 250 using namespace std; typedef long long ll; int n, m, q; vector<pair<int, int> > vec[100002]; vector<int> link[100002]; vector<int> revLink[100002]; bool chk[100002]; int DP[100002]; int ans; int main(){ scanf("%d %d %d", &n, &m, &q); for(int i=1; i<=m; i++){ int x, y; scanf("%d %d", &x, &y); link[x].push_back(y); revLink[y].push_back(x); } for(int i=1; i<=n; i++){ if(revLink[i].empty()){ vec[i].push_back(make_pair(i, 0)); continue; } vector<pair<int, int> > va, vb, vret; va.push_back(make_pair(i, 0)); for(auto prv: revLink[i]){ vb = vec[prv]; for(auto &val: vb) val.second++; vret.clear(); int vaPnt = 0, vbPnt = 0; while(vaPnt < (int)va.size() && vbPnt < (int)vb.size() && (int)vret.size() <= LIM){ if(chk[va[vaPnt].first]) vaPnt++; else if(chk[vb[vbPnt].first]) vbPnt++; else if(va[vaPnt].second > vb[vbPnt].second) chk[va[vaPnt].first] = 1, vret.push_back(va[vaPnt++]); else chk[vb[vbPnt].first] = 1, vret.push_back(vb[vbPnt++]); } while(vaPnt < (int)va.size() && (int)vret.size() <= LIM){ if(chk[va[vaPnt].first]) vaPnt++; else chk[va[vaPnt].first] = 1, vret.push_back(va[vaPnt++]); } while(vbPnt < (int)vb.size() && (int)vret.size() <= LIM){ if(chk[vb[vbPnt].first]) vaPnt++; else chk[vb[vbPnt].first] = 1, vret.push_back(vb[vbPnt++]); } for(auto p: vret) chk[p.first] = 0; va.swap(vret); } vec[i].swap(va); } for(int i=1; i<=q; i++){ int t, y; vector<int> lst; scanf("%d %d", &t, &y); for(int i=0; i<y; i++){ int tmpx; scanf("%d", &tmpx); lst.push_back(tmpx); } if(y <= LIM){ for(auto x: lst) chk[x] = 1; int ans = -1; for(auto x: vec[t]){ if(chk[x.first]) continue; ans = x.second; break; } printf("%d\n", ans); for(auto x: lst) chk[x] = 0; } else{ for(auto x: lst) chk[x] = 1; for(int i=1; i<=n; i++) DP[i] = -1e9; DP[t] = 0; ans = -1; for(int i=t; i>=1; i--){ for(auto y: link[i]) DP[i] = max(DP[i], DP[y]+1); if(!chk[i]) ans = max(ans, DP[i]); } printf("%d\n", ans); for(auto x: lst) chk[x] = 0; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 4 ms | 7252 KB | Output is correct |
3 | Correct | 4 ms | 7356 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 6 ms | 7892 KB | Output is correct |
6 | Correct | 7 ms | 7892 KB | Output is correct |
7 | Correct | 6 ms | 7872 KB | Output is correct |
8 | Correct | 10 ms | 9300 KB | Output is correct |
9 | Correct | 10 ms | 9224 KB | Output is correct |
10 | Correct | 9 ms | 9300 KB | Output is correct |
11 | Correct | 9 ms | 9172 KB | Output is correct |
12 | Correct | 8 ms | 8584 KB | Output is correct |
13 | Correct | 9 ms | 9092 KB | Output is correct |
14 | Correct | 9 ms | 8524 KB | Output is correct |
15 | Correct | 7 ms | 7988 KB | Output is correct |
16 | Correct | 8 ms | 8520 KB | Output is correct |
17 | Correct | 9 ms | 8708 KB | Output is correct |
18 | Correct | 8 ms | 8324 KB | Output is correct |
19 | Correct | 9 ms | 8788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 4 ms | 7252 KB | Output is correct |
3 | Correct | 4 ms | 7356 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 6 ms | 7892 KB | Output is correct |
6 | Correct | 7 ms | 7892 KB | Output is correct |
7 | Correct | 6 ms | 7872 KB | Output is correct |
8 | Correct | 10 ms | 9300 KB | Output is correct |
9 | Correct | 10 ms | 9224 KB | Output is correct |
10 | Correct | 9 ms | 9300 KB | Output is correct |
11 | Correct | 9 ms | 9172 KB | Output is correct |
12 | Correct | 8 ms | 8584 KB | Output is correct |
13 | Correct | 9 ms | 9092 KB | Output is correct |
14 | Correct | 9 ms | 8524 KB | Output is correct |
15 | Correct | 7 ms | 7988 KB | Output is correct |
16 | Correct | 8 ms | 8520 KB | Output is correct |
17 | Correct | 9 ms | 8708 KB | Output is correct |
18 | Correct | 8 ms | 8324 KB | Output is correct |
19 | Correct | 9 ms | 8788 KB | Output is correct |
20 | Correct | 437 ms | 13180 KB | Output is correct |
21 | Correct | 415 ms | 13128 KB | Output is correct |
22 | Correct | 436 ms | 13268 KB | Output is correct |
23 | Correct | 469 ms | 13112 KB | Output is correct |
24 | Correct | 691 ms | 159876 KB | Output is correct |
25 | Correct | 737 ms | 164516 KB | Output is correct |
26 | Correct | 749 ms | 164660 KB | Output is correct |
27 | Correct | 786 ms | 219076 KB | Output is correct |
28 | Correct | 796 ms | 219208 KB | Output is correct |
29 | Correct | 747 ms | 219136 KB | Output is correct |
30 | Correct | 742 ms | 218296 KB | Output is correct |
31 | Correct | 772 ms | 213116 KB | Output is correct |
32 | Correct | 782 ms | 218260 KB | Output is correct |
33 | Correct | 633 ms | 140832 KB | Output is correct |
34 | Correct | 523 ms | 122268 KB | Output is correct |
35 | Correct | 605 ms | 140044 KB | Output is correct |
36 | Correct | 716 ms | 179956 KB | Output is correct |
37 | Correct | 676 ms | 167908 KB | Output is correct |
38 | Correct | 707 ms | 180592 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 4 ms | 7252 KB | Output is correct |
3 | Correct | 4 ms | 7356 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 6 ms | 7892 KB | Output is correct |
6 | Correct | 7 ms | 7892 KB | Output is correct |
7 | Correct | 6 ms | 7872 KB | Output is correct |
8 | Correct | 10 ms | 9300 KB | Output is correct |
9 | Correct | 10 ms | 9224 KB | Output is correct |
10 | Correct | 9 ms | 9300 KB | Output is correct |
11 | Correct | 9 ms | 9172 KB | Output is correct |
12 | Correct | 8 ms | 8584 KB | Output is correct |
13 | Correct | 9 ms | 9092 KB | Output is correct |
14 | Correct | 9 ms | 8524 KB | Output is correct |
15 | Correct | 7 ms | 7988 KB | Output is correct |
16 | Correct | 8 ms | 8520 KB | Output is correct |
17 | Correct | 9 ms | 8708 KB | Output is correct |
18 | Correct | 8 ms | 8324 KB | Output is correct |
19 | Correct | 9 ms | 8788 KB | Output is correct |
20 | Correct | 437 ms | 13180 KB | Output is correct |
21 | Correct | 415 ms | 13128 KB | Output is correct |
22 | Correct | 436 ms | 13268 KB | Output is correct |
23 | Correct | 469 ms | 13112 KB | Output is correct |
24 | Correct | 691 ms | 159876 KB | Output is correct |
25 | Correct | 737 ms | 164516 KB | Output is correct |
26 | Correct | 749 ms | 164660 KB | Output is correct |
27 | Correct | 786 ms | 219076 KB | Output is correct |
28 | Correct | 796 ms | 219208 KB | Output is correct |
29 | Correct | 747 ms | 219136 KB | Output is correct |
30 | Correct | 742 ms | 218296 KB | Output is correct |
31 | Correct | 772 ms | 213116 KB | Output is correct |
32 | Correct | 782 ms | 218260 KB | Output is correct |
33 | Correct | 633 ms | 140832 KB | Output is correct |
34 | Correct | 523 ms | 122268 KB | Output is correct |
35 | Correct | 605 ms | 140044 KB | Output is correct |
36 | Correct | 716 ms | 179956 KB | Output is correct |
37 | Correct | 676 ms | 167908 KB | Output is correct |
38 | Correct | 707 ms | 180592 KB | Output is correct |
39 | Correct | 781 ms | 161740 KB | Output is correct |
40 | Correct | 722 ms | 162636 KB | Output is correct |
41 | Correct | 711 ms | 162892 KB | Output is correct |
42 | Correct | 848 ms | 162724 KB | Output is correct |
43 | Correct | 708 ms | 161996 KB | Output is correct |
44 | Correct | 481 ms | 14424 KB | Output is correct |
45 | Correct | 438 ms | 13776 KB | Output is correct |
46 | Correct | 458 ms | 13512 KB | Output is correct |
47 | Correct | 446 ms | 13252 KB | Output is correct |
48 | Correct | 420 ms | 13096 KB | Output is correct |
49 | Correct | 1499 ms | 219588 KB | Output is correct |
50 | Correct | 929 ms | 218304 KB | Output is correct |
51 | Correct | 457 ms | 14264 KB | Output is correct |
52 | Correct | 426 ms | 13392 KB | Output is correct |
53 | Correct | 752 ms | 179996 KB | Output is correct |
54 | Correct | 724 ms | 167992 KB | Output is correct |
55 | Correct | 663 ms | 179004 KB | Output is correct |
56 | Correct | 711 ms | 167740 KB | Output is correct |
57 | Correct | 473 ms | 14340 KB | Output is correct |
58 | Correct | 450 ms | 14284 KB | Output is correct |
59 | Correct | 436 ms | 13412 KB | Output is correct |
60 | Correct | 435 ms | 13448 KB | Output is correct |
61 | Correct | 1269 ms | 218776 KB | Output is correct |
62 | Correct | 793 ms | 180128 KB | Output is correct |
63 | Correct | 783 ms | 167284 KB | Output is correct |
64 | Correct | 1158 ms | 218844 KB | Output is correct |
65 | Correct | 964 ms | 179300 KB | Output is correct |
66 | Correct | 1016 ms | 168300 KB | Output is correct |
67 | Correct | 767 ms | 218428 KB | Output is correct |
68 | Correct | 677 ms | 179536 KB | Output is correct |
69 | Correct | 674 ms | 165784 KB | Output is correct |
70 | Correct | 778 ms | 219040 KB | Output is correct |
71 | Correct | 713 ms | 180096 KB | Output is correct |
72 | Correct | 706 ms | 167960 KB | Output is correct |
73 | Correct | 808 ms | 218984 KB | Output is correct |
74 | Correct | 735 ms | 179952 KB | Output is correct |
75 | Correct | 729 ms | 167624 KB | Output is correct |
76 | Correct | 839 ms | 220028 KB | Output is correct |
77 | Correct | 770 ms | 218688 KB | Output is correct |
78 | Correct | 792 ms | 219268 KB | Output is correct |
79 | Correct | 500 ms | 14404 KB | Output is correct |
80 | Correct | 453 ms | 13508 KB | Output is correct |
81 | Correct | 420 ms | 13132 KB | Output is correct |
82 | Correct | 838 ms | 219144 KB | Output is correct |
83 | Correct | 853 ms | 214012 KB | Output is correct |
84 | Correct | 762 ms | 217960 KB | Output is correct |
85 | Correct | 791 ms | 212672 KB | Output is correct |
86 | Correct | 794 ms | 218500 KB | Output is correct |
87 | Correct | 805 ms | 213576 KB | Output is correct |
88 | Correct | 470 ms | 14524 KB | Output is correct |
89 | Correct | 478 ms | 14648 KB | Output is correct |
90 | Correct | 443 ms | 13444 KB | Output is correct |
91 | Correct | 423 ms | 13516 KB | Output is correct |
92 | Correct | 421 ms | 13152 KB | Output is correct |
93 | Correct | 427 ms | 13096 KB | Output is correct |
94 | Correct | 672 ms | 141624 KB | Output is correct |
95 | Correct | 586 ms | 122280 KB | Output is correct |
96 | Correct | 574 ms | 139832 KB | Output is correct |
97 | Correct | 527 ms | 123264 KB | Output is correct |
98 | Correct | 572 ms | 140860 KB | Output is correct |
99 | Correct | 557 ms | 123332 KB | Output is correct |
100 | Correct | 470 ms | 14464 KB | Output is correct |
101 | Correct | 484 ms | 14412 KB | Output is correct |
102 | Correct | 454 ms | 13440 KB | Output is correct |
103 | Correct | 441 ms | 13552 KB | Output is correct |
104 | Correct | 447 ms | 13084 KB | Output is correct |
105 | Correct | 438 ms | 13284 KB | Output is correct |
106 | Correct | 710 ms | 180248 KB | Output is correct |
107 | Correct | 735 ms | 168540 KB | Output is correct |
108 | Correct | 671 ms | 180032 KB | Output is correct |
109 | Correct | 679 ms | 167140 KB | Output is correct |
110 | Correct | 677 ms | 180848 KB | Output is correct |
111 | Correct | 700 ms | 168452 KB | Output is correct |
112 | Correct | 461 ms | 14420 KB | Output is correct |
113 | Correct | 454 ms | 14496 KB | Output is correct |
114 | Correct | 436 ms | 13624 KB | Output is correct |
115 | Correct | 433 ms | 13444 KB | Output is correct |
116 | Correct | 410 ms | 13116 KB | Output is correct |
117 | Correct | 419 ms | 13120 KB | Output is correct |
118 | Correct | 763 ms | 218336 KB | Output is correct |
119 | Correct | 669 ms | 179700 KB | Output is correct |
120 | Correct | 660 ms | 166892 KB | Output is correct |
121 | Correct | 753 ms | 218436 KB | Output is correct |
122 | Correct | 682 ms | 179232 KB | Output is correct |
123 | Correct | 667 ms | 166792 KB | Output is correct |
124 | Correct | 743 ms | 218352 KB | Output is correct |
125 | Correct | 662 ms | 180032 KB | Output is correct |
126 | Correct | 653 ms | 166460 KB | Output is correct |