QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133962 | #4938. Writing Tasks | Rd_rainydays | WA | 140ms | 84616kb | C++20 | 4.1kb | 2023-08-02 18:53:35 | 2023-08-02 18:53:39 |
Judging History
answer
#include <bits/stdc++.h>
using std::vector;
using std::tuple;
#define all(x) (x).begin(), (x).end()
const int N = 400005;
int A, C, T;
vector<int> L[N], F[N], S[N], ps[N];
int tot;
vector<tuple<int, int>> es;
vector<int> adj[N];
std::map<tuple<int, int>, int> id;
vector<int> vs[N];
bool vis[N];
void solve() {
for (int i = 1; i <= tot; i++)
assert(adj[i].size() <= 2u);
vector<int> ids;
bool isRing = 0;
int head = -1;
auto dfs = [&](int x, int f, auto& dfs) -> void {
ids.push_back(x);
// printf(" dfs log : %d\n", x);
vis[x] = 1;
if (adj[x].size() == 1u && head == -1) head = x;
for (auto y : adj[x]) if (y != f) {
if (vis[y] == 1) { isRing = 1; break; }
dfs(y, x, dfs);
}
};
int ans = 0;
for (int i = 1; i <= tot; i++) {
if (vis[i]) continue;
isRing = 0, head = -1;
ids.clear();
dfs(i, 0, dfs);
if (head != -1 && !isRing) std::reverse(ids.begin(), std::find(all(ids), head) + 1);
// printf(" %s :", (isRing ? "Ring" : "Chain"));
// for (int id : ids)
// printf(" %d ", id);
// puts("");
vector<std::array<int, 3>> dp(ids.size());
auto do_trans = [&](int exclude) -> int {
for (int j = 1; j < (int)ids.size(); j++) {
int cur = ids[j], pre = ids[j - 1];
for (int t = 0; t < (int)vs[cur].size(); t++)
dp[j][t + 1] = dp[j - 1][0] + 1;
dp[j][0] = *std::max_element(all(dp[j - 1]));
// trivial
for (int t = 0; t < (int)vs[cur].size(); t++)
for (int s = 0; s < (int)vs[pre].size(); s++) {
if (vs[cur][t] == vs[pre][s]) continue;
dp[j][t + 1] = std::max(dp[j][t + 1], dp[j - 1][s + 1] + 1);
}
}
int cur_ans = 0;
for (int i = 0; i < 3; i++) {
if (i == exclude && exclude > 0) continue;
cur_ans = std::max(cur_ans, dp.back()[i]);
}
return cur_ans;
};
if (!isRing) {
dp.assign(ids.size(), {0, 0, 0});
dp[0][0] = 0;
for (int t = 0; t < (int)vs[ids[0]].size(); t++)
dp[0][t + 1] = 1;
ans += do_trans(0);
} else {
vector<int> cadi;
for (int ex = 0; ex <= (int)vs[ids[0]].size(); ex++) {
dp.assign(ids.size(), {0, 0, 0});
dp[0][ex] = (ex > 0);
cadi.push_back(do_trans(ex));
}
ans += *std::max_element(all(cadi));
}
// printf(" >> %d\n", ans);
}
printf("%d\n", ans);
return;
}
int main() {
scanf("%d%d%d", &A, &C, &T);
for (int i = 1; i <= A; i++) {
int sz;
scanf("%d", &sz);
L[i].resize(sz);
for (auto &x : L[i]) scanf("%d", &x);
}
for (int i = 1; i <= A; i++) {
int sz;
scanf("%d", &sz);
F[i].resize(sz);
for (auto &x : F[i]) scanf("%d", &x);
}
for (int i = 1; i <= C; i++) {
int sz;
scanf("%d", &sz);
S[i].resize(sz);
for (auto &x : S[i]) {
scanf("%d", &x);
++tot;
ps[x].push_back(tot);
id[{i, x}] = tot;
}
if (sz == 2)
es.emplace_back(tot - 1, tot);
}
for (int i = 1; i <= T; i++)
if ((int)ps[i].size() == 2)
es.emplace_back(ps[i][0], ps[i][1]);
for (int i = 1; i <= A; i++)
for (auto l : L[i]) for (auto f : F[i])
if (id.count({l, f}))
vs[id[{l, f}]].push_back(i);
for (int i = 1; i <= tot; i++)
assert(vs[i].size() <= 2u);
for (auto &[a, b] : es)
if (a > b) std::swap(a, b);
std::sort(all(es));
es.erase(std::unique(all(es)), es.end());
for (auto [a, b] : es) {
adj[a].push_back(b);
adj[b].push_back(a);
}
solve();
return 0;
}
/*
15 15 20
2 12 14
2 1 3
1 11
2 5 13
2 8 9
1 13
1 9
2 15 11
2 3 6
2 6 7
1 10
1 2
2 7 12
1 14
1 4
1 3
1 1
2 12 20
2 18 2
2 10 15
2 2 10
2 15 18
2 17 3
2 6 7
2 16 17
1 19
2 13 6
1 14
2 4 11
2 8 16
2 1 4
1 13
2 6 1
1 8
1 18
2 16 7
1 14
2 10 11
2 15 19
2 19 18
1 12
1 3
1 2
2 4 16
2 17 15
2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2
3 4 3
1 2
2 4 2
2 1 3
1 1
2 2 3
2 3 2
1 3
2 1 3
1 2
1 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 59968kb
input:
2 3 2 2 1 2 2 2 3 1 1 1 1 1 1 1 1 1 2
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 59972kb
input:
2 2 2 0 1 2 0 2 1 2 2 1 2 0
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 111ms
memory: 74956kb
input:
40623 39265 42226 2 14643 37432 2 29610 20181 2 6441 7614 2 17559 3238 2 39001 17644 2 6431 37097 2 6347 12246 2 1130 1688 2 38583 9078 2 8746 27832 2 13090 39048 2 32647 18777 2 27505 19277 2 31201 25824 2 6133 20344 2 11625 20997 2 18528 35730 0 2 22986 5273 2 10942 38791 2 19025 35679 2 32321 124...
output:
78528
result:
ok single line: '78528'
Test #4:
score: 0
Accepted
time: 116ms
memory: 74964kb
input:
41022 39421 42288 2 26413 2168 2 24182 14199 2 18798 17846 2 3398 19624 2 16796 33998 2 7209 25883 2 26356 13537 2 56 30294 2 34909 20218 2 29727 22116 2 16349 1704 2 9254 18036 2 16197 16096 2 21562 31470 2 14773 10518 2 38025 12573 2 15509 32276 2 9613 12321 2 19146 11395 2 7186 36431 0 2 10098 22...
output:
78840
result:
ok single line: '78840'
Test #5:
score: 0
Accepted
time: 117ms
memory: 76664kb
input:
49395 43808 45888 2 13031 11323 2 41375 4393 2 32137 17908 2 29053 42691 0 2 38335 30970 2 38318 43773 2 22999 22444 0 2 39248 30837 0 2 29807 2360 2 29363 3536 2 8515 41137 2 7890 31441 0 2 31070 6987 2 24295 15517 2 14204 13069 2 32996 40146 2 38164 1478 2 40032 19143 0 2 18430 24119 2 37845 33290...
output:
87616
result:
ok single line: '87616'
Test #6:
score: 0
Accepted
time: 4ms
memory: 59916kb
input:
3 4 3 1 2 2 4 2 2 1 3 1 1 2 2 3 2 3 2 1 3 2 1 3 1 2 1 2
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 4ms
memory: 59976kb
input:
15 17 18 1 12 2 13 4 2 2 6 2 11 14 2 7 3 2 17 11 2 4 8 2 5 1 1 1 1 16 1 3 2 10 16 1 8 2 15 5 1 6 2 6 1 2 7 3 1 13 2 12 9 2 8 18 1 9 2 1 15 2 5 13 2 18 14 2 15 7 1 4 2 10 2 1 2 1 17 2 14 17 1 18 1 13 1 4 1 1 1 5 2 14 3 2 8 16 2 2 16 1 10 1 10 2 12 14 1 6 2 7 15 2 6 3 2 17 12 1 15 1 9
output:
15
result:
ok single line: '15'
Test #8:
score: 0
Accepted
time: 4ms
memory: 60312kb
input:
769 869 792 1 254 2 210 794 1 863 2 40 403 2 279 773 2 54 328 2 196 473 1 804 1 261 1 174 1 219 1 22 1 429 1 195 2 769 100 1 33 1 457 1 604 2 473 714 2 423 227 2 453 654 1 864 2 220 243 2 520 321 2 421 805 2 721 11 2 216 793 1 360 1 169 2 121 613 2 714 594 1 692 2 642 607 2 538 781 2 800 387 2 494 5...
output:
769
result:
ok single line: '769'
Test #9:
score: 0
Accepted
time: 76ms
memory: 71900kb
input:
46352 41211 38602 2 11300 5679 2 2876 4114 2 28525 6628 1 23785 1 30940 1 26982 1 8056 1 13748 2 25254 21974 1 3446 2 2294 13453 0 1 16724 2 36970 18406 2 7688 17413 1 25901 1 39238 1 16098 1 29911 2 15113 849 1 31293 2 32195 13287 0 1 12670 2 40732 19567 2 24195 23787 1 40913 2 18820 10009 0 0 2 23...
output:
38602
result:
ok single line: '38602'
Test #10:
score: 0
Accepted
time: 4ms
memory: 60056kb
input:
3 4 3 1 4 2 1 3 2 3 4 2 1 2 2 3 1 1 2 1 3 0 1 2 2 1 2
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 9ms
memory: 59992kb
input:
15 15 20 2 12 14 2 1 3 1 11 2 5 13 2 8 9 1 13 1 9 2 15 11 2 3 6 2 6 7 1 10 1 2 2 7 12 1 14 1 4 1 3 1 1 2 12 20 2 18 2 2 10 15 2 2 10 2 15 18 2 17 3 2 6 7 2 16 17 1 19 2 13 6 1 14 2 4 11 2 8 16 2 1 4 1 13 2 6 1 1 8 1 18 2 16 7 1 14 2 10 11 2 15 19 2 19 18 1 12 1 3 1 2 2 4 16 2 17 15
output:
16
result:
ok single line: '16'
Test #12:
score: 0
Accepted
time: 7ms
memory: 60304kb
input:
942 753 814 2 429 543 1 228 1 442 0 0 2 215 635 1 199 2 735 727 1 335 2 56 209 2 668 570 2 748 190 2 719 571 0 1 650 1 468 1 646 2 150 547 2 551 53 0 1 203 0 2 544 664 1 100 2 388 321 1 94 1 77 2 535 253 1 306 0 2 753 342 2 690 529 2 204 712 2 621 693 1 253 1 549 2 712 639 2 43 323 2 206 585 2 82 45...
output:
753
result:
ok single line: '753'
Test #13:
score: 0
Accepted
time: 4ms
memory: 60040kb
input:
15 20 16 2 8 7 2 7 13 2 11 20 2 4 9 2 18 6 2 10 13 2 11 5 2 10 3 2 8 1 2 12 5 2 9 2 2 17 3 2 20 1 2 17 18 2 16 19 2 4 12 2 7 6 2 11 13 2 8 3 2 7 3 2 11 14 1 9 2 5 2 2 6 13 2 15 1 2 14 1 2 15 2 2 9 10 2 12 5 2 8 4 2 9 8 2 9 6 2 7 16 2 14 10 2 10 8 2 1 13 1 15 1 16 2 11 5 2 11 12 2 14 3 0 2 4 13 2 7 1...
output:
5
result:
ok single line: '5'
Test #14:
score: 0
Accepted
time: 79ms
memory: 72644kb
input:
48398 47836 40164 2 18023 23816 0 0 1 14256 1 47537 2 40419 28208 2 24335 20756 2 11563 31099 2 11298 27901 1 43928 1 4795 2 33599 41395 1 40893 2 24858 20153 1 16524 2 73 9844 2 18804 12559 1 47263 1 36093 2 19492 7210 2 10991 38704 2 44074 26169 1 9493 2 23707 40251 1 19203 2 14974 45727 1 15661 2...
output:
40164
result:
ok single line: '40164'
Test #15:
score: 0
Accepted
time: 4ms
memory: 59980kb
input:
4 5 4 2 2 4 1 3 1 4 2 1 3 1 2 1 4 2 1 3 2 3 4 2 3 1 2 2 3 1 4 1 1 0
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 8ms
memory: 59980kb
input:
19 20 20 1 16 2 10 7 1 13 2 11 2 1 8 1 7 2 20 17 2 5 13 1 2 2 6 8 2 3 15 2 9 5 1 4 1 18 2 19 1 2 12 1 2 14 19 2 17 11 1 15 1 8 1 10 1 13 2 17 1 2 20 4 2 16 6 2 4 9 1 14 1 5 1 7 1 18 1 15 1 1 2 6 11 2 2 16 2 9 14 2 3 17 1 19 1 12 0 1 5 1 18 2 1 8 2 14 12 2 7 2 1 16 2 20 5 2 15 11 2 10 13 2 17 1 2 9 4...
output:
19
result:
ok single line: '19'
Test #17:
score: 0
Accepted
time: 4ms
memory: 60232kb
input:
858 936 831 1 78 2 132 126 0 2 761 378 1 914 1 36 2 884 480 2 344 531 2 718 395 2 30 270 2 503 495 2 717 520 1 833 2 483 636 1 498 2 181 250 2 538 311 0 2 246 552 1 201 2 598 595 2 672 747 2 823 508 2 429 369 1 705 2 929 659 1 866 2 423 31 2 425 921 2 422 313 2 927 726 1 194 2 553 919 2 733 323 1 12...
output:
831
result:
ok single line: '831'
Test #18:
score: 0
Accepted
time: 75ms
memory: 72948kb
input:
49781 42895 45291 1 29407 1 9103 2 5324 6026 1 31374 2 5841 29212 2 23318 30169 0 2 25579 21864 1 32335 2 23800 806 2 25593 11060 2 15157 69 1 34355 2 2925 14080 2 33167 18126 2 7104 5549 2 40443 5056 2 28415 696 1 4790 1 7018 2 3471 21650 2 2916 40765 1 34240 2 42308 18364 1 38483 0 2 1698 11488 1 ...
output:
42895
result:
ok single line: '42895'
Test #19:
score: 0
Accepted
time: 8ms
memory: 59992kb
input:
2 2 2 1 2 2 2 1 1 1 2 1 2 2 1 2 1 1
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 6ms
memory: 60040kb
input:
2 2 2 1 2 2 2 1 1 2 2 2 1 2 2 1 1 2
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 48ms
memory: 69060kb
input:
19293 19293 19293 2 15559 6355 2 18678 12383 2 10518 2914 2 9321 5480 2 2515 9636 2 348 6411 2 8068 5686 2 13171 5869 2 3983 3883 2 11207 18235 2 6332 13692 2 9259 8353 2 18013 1039 2 14419 10593 2 14504 3897 2 3936 12241 2 7111 14415 2 9387 11892 2 6697 4039 2 8091 9046 2 4286 14361 2 17222 5305 2 ...
output:
28939
result:
ok single line: '28939'
Test #22:
score: 0
Accepted
time: 3ms
memory: 60092kb
input:
20 20 20 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 0 0 0 0 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 0 0 0 0 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2...
output:
22
result:
ok single line: '22'
Test #23:
score: 0
Accepted
time: 4ms
memory: 60544kb
input:
1000 1000 1000 1 1 2 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 8 2 8 9 2 9 10 2 10 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 2 16 17 2 17 18 2 18 19 2 19 20 2 20 21 1 22 2 22 23 2 23 24 2 24 25 2 25 26 2 26 27 2 27 28 2 28 29 2 29 30 2 30 31 2 31 32 2 32 33 2 33 34 2 34 35 2 35 36 2 36 37 2 37 38 2 38 ...
output:
1292
result:
ok single line: '1292'
Test #24:
score: 0
Accepted
time: 94ms
memory: 73524kb
input:
42099 49103 43206 2 2436 21573 2 9996 23380 2 18655 46120 2 12927 46150 2 40795 5903 2 21860 35021 2 35508 10085 2 15704 5818 2 4284 22266 2 21850 28412 2 25375 24412 2 5997 38671 2 14067 26688 2 29986 225 2 8819 39574 2 28550 12704 2 6055 4336 2 14012 21939 2 13223 10017 2 36352 23453 2 41234 13597...
output:
6
result:
ok single line: '6'
Test #25:
score: 0
Accepted
time: 80ms
memory: 76456kb
input:
50000 50000 50000 1 1 2 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 8 2 8 9 2 9 10 2 10 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 2 16 17 2 17 18 2 18 19 2 19 20 2 20 21 2 21 22 2 22 23 2 23 24 2 24 25 2 25 26 2 26 27 2 27 28 2 28 29 2 29 30 2 30 31 2 31 32 2 32 33 2 33 34 2 34 35 2 35 36 2 36 37 2 37 38...
output:
65098
result:
ok single line: '65098'
Test #26:
score: 0
Accepted
time: 9ms
memory: 60468kb
input:
797 781 965 2 542 265 2 613 195 2 483 758 2 387 62 2 9 45 2 146 38 2 305 457 2 374 18 2 776 273 2 475 432 2 691 108 2 264 284 2 70 598 2 741 673 2 393 480 2 250 145 2 740 748 2 35 221 2 442 229 2 204 326 2 304 538 2 721 685 2 58 778 2 51 740 2 750 227 2 25 389 2 142 462 2 557 370 2 30 147 2 28 300 2...
output:
960
result:
ok single line: '960'
Test #27:
score: 0
Accepted
time: 115ms
memory: 74572kb
input:
48703 42977 49346 2 8620 24764 2 14087 32876 0 2 8945 5627 2 41296 34519 0 2 29062 5131 2 816 1371 2 29401 1787 0 2 10358 19458 2 611 26890 2 32600 33419 2 7484 25258 2 18804 27934 2 40145 24038 2 10559 8176 2 17733 7525 2 12422 37383 2 1438 41231 2 40252 30643 0 0 2 6532 38724 2 19246 9753 2 19848 ...
output:
56108
result:
ok single line: '56108'
Test #28:
score: 0
Accepted
time: 3ms
memory: 60712kb
input:
802 787 751 2 138 295 2 572 302 2 575 580 2 556 248 2 642 441 2 638 379 2 650 79 2 397 313 2 464 757 2 753 483 2 461 61 2 506 367 2 582 62 2 350 616 2 19 284 2 196 658 2 483 683 2 588 526 2 106 333 2 478 23 2 640 442 2 781 525 2 362 193 2 323 691 2 648 627 2 784 355 2 399 51 2 662 105 2 107 53 2 417...
output:
928
result:
ok single line: '928'
Test #29:
score: 0
Accepted
time: 99ms
memory: 74156kb
input:
41866 41104 47356 2 14498 27153 2 11889 11501 2 24507 26825 2 9375 38374 2 36646 26596 2 27810 2781 2 18125 31616 2 28814 7751 2 3726 32390 2 24020 9158 2 23175 26847 2 30193 20375 2 33609 14680 2 12657 26318 2 36465 1173 2 40844 30906 0 2 17851 11228 2 15337 33580 0 2 35061 16536 2 1967 3490 2 1256...
output:
54184
result:
ok single line: '54184'
Test #30:
score: 0
Accepted
time: 14ms
memory: 60292kb
input:
849 766 854 1 150 2 721 416 2 716 277 1 336 2 471 535 1 621 2 661 638 2 201 751 0 2 705 67 2 350 24 2 118 131 2 124 704 2 66 511 2 577 200 2 406 733 2 749 312 0 2 114 168 2 472 18 2 83 398 2 261 591 2 627 433 2 60 454 2 371 351 2 70 706 2 143 35 2 477 133 2 365 38 1 126 1 525 2 587 74 0 2 162 225 2 ...
output:
935
result:
ok single line: '935'
Test #31:
score: 0
Accepted
time: 104ms
memory: 74136kb
input:
40473 42204 46693 2 17306 29840 2 21655 27206 2 1577 30755 2 9303 38135 2 13899 38726 2 25718 5486 0 2 13674 32709 2 3258 1310 2 19078 6271 2 32222 38810 2 18668 28018 2 9005 31601 2 31888 40637 2 32991 7539 2 40415 29067 2 33572 39589 2 26823 19361 2 38360 8413 2 4352 12745 2 40742 38924 2 14996 19...
output:
53046
result:
ok single line: '53046'
Test #32:
score: 0
Accepted
time: 3ms
memory: 60396kb
input:
3 3 3 2 3 1 2 2 1 2 3 2 2 1 3 2 2 3 2 1 2 2 2 3 2 1 2 2 1 3
output:
4
result:
ok single line: '4'
Test #33:
score: 0
Accepted
time: 12ms
memory: 60056kb
input:
4 4 4 2 3 2 2 3 4 2 1 2 2 4 1 2 2 3 2 2 4 2 1 3 2 4 1 2 4 1 2 1 3 2 2 3 2 2 4
output:
6
result:
ok single line: '6'
Test #34:
score: 0
Accepted
time: 140ms
memory: 84616kb
input:
50000 50000 50000 2 45046 28892 2 26220 33823 2 46837 49104 2 3917 21543 2 22880 20259 2 25075 24819 2 28379 7777 2 801 36871 2 44187 21466 2 8706 16158 2 15338 39721 2 39723 29802 2 34539 5470 2 10200 49750 2 21699 20778 2 6058 31648 2 38204 40071 2 23548 503 2 49337 49734 2 38822 41362 2 47146 283...
output:
75000
result:
ok single line: '75000'
Test #35:
score: 0
Accepted
time: 4ms
memory: 60052kb
input:
1 1 2 0 0 0
output:
0
result:
ok single line: '0'
Test #36:
score: -100
Wrong Answer
time: 93ms
memory: 73572kb
input:
39951 46036 43531 2 35094 23951 2 18866 21023 2 32805 10424 2 35955 45509 2 189 5168 2 34865 13037 2 8649 20563 2 24042 31856 2 25255 38915 2 7464 35453 2 25282 29391 1 20283 0 2 34325 20208 2 4126 28607 2 30645 33252 2 16224 5621 2 785 29439 0 2 4746 31449 2 27519 15163 2 41348 17178 2 42965 18260 ...
output:
51969
result:
wrong answer 1st lines differ - expected: '51923', found: '51969'