QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133954 | #4938. Writing Tasks | Rd_rainydays | WA | 104ms | 76732kb | C++20 | 3.6kb | 2023-08-02 18:15:55 | 2023-08-02 18:15:59 |
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 = 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])
vs[id[{l, f}]].push_back(i);
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;
}
/*
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
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 59976kb
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: 1ms
memory: 60052kb
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: 88ms
memory: 74908kb
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: 81ms
memory: 75060kb
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: 104ms
memory: 76732kb
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: 59976kb
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: 8ms
memory: 60316kb
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: 9ms
memory: 60652kb
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: 83ms
memory: 75252kb
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: 8ms
memory: 59984kb
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: -100
Wrong Answer
time: 13ms
memory: 60060kb
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:
17
result:
wrong answer 1st lines differ - expected: '16', found: '17'