QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133938 | #4938. Writing Tasks | Rd_rainydays | TL | 8ms | 59972kb | C++20 | 3.0kb | 2023-08-02 17:50:13 | 2023-08-02 17:50:16 |
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<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;
auto dfs = [&](int x, int f, auto& dfs) -> void {
ids.push_back(x);
vis[x] = 1;
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;
dfs(i, 0, dfs);
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] = std::max(dp[j][t], dp[j - 1][s] + 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 <= 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);
}
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) {
adj[tot].push_back(tot - 1);
adj[tot - 1].push_back(tot);
}
}
for (int i = 1; i <= T; i++)
if ((int)ps[i].size() == 2) {
adj[ps[i][0]].push_back(ps[i][1]);
adj[ps[i][1]].push_back(ps[i][0]);
}
for (int i = 1; i <= A; i++)
for (auto l : L[i]) for (auto f : F[i])
vs[id[{l, f}]].push_back(i);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 59972kb
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: 4ms
memory: 59968kb
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: -100
Time Limit Exceeded
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...