QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130970 | #4938. Writing Tasks | karuna | TL | 5ms | 19356kb | C++17 | 4.1kb | 2023-07-25 22:30:00 | 2023-07-25 22:30:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 202020;
int n, src, snk, N1, N2, N3;
vector<int> G[3][3][MAXN / 4];
set<pair<int, int>> S1, S2, S3;
map<array<int, 3>, int> mp;
int f(int x, int y, int z) {
if (mp.find({x, y, z}) == mp.end()) {
mp[{x, y, z}] = 1 + mp.size();
}
return mp[{x, y, z}];
}
vector<int> gph[MAXN];
vector<int> vec;
int vis[MAXN];
void dfs(int v) {
if (vis[v]) return;
vis[v] = 1;
vec.push_back(v);
for (int x : gph[v]) dfs(x);
}
int dp[2][MAXN];
void solve(int p, int v) {
for (int x : gph[v]) if (p != x) {
solve(v, x);
dp[0][v] += max(dp[1][x], dp[0][x]);
dp[1][v] += dp[0][x];
}
dp[1][v]++;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N1 >> N2 >> N3;
for (int i = 1; i <= N1; i++) {
int n; cin >> n;
for (int j = 0; j < n; j++) {
int x; cin >> x;
S1.insert({i, x});
G[0][1][i].push_back(x);
G[1][0][x].push_back(i);
}
}
for (int i = 1; i <= N1; i++) {
int n; cin >> n;
for (int j = 0; j < n; j++) {
int x; cin >> x;
S2.insert({i, x});
G[0][2][i].push_back(x);
G[2][0][x].push_back(i);
}
}
for (int i = 1; i <= N2; i++) {
int n; cin >> n;
for (int j = 0; j < n; j++) {
int x; cin >> x;
S3.insert({i, x});
G[1][2][i].push_back(x);
G[2][1][x].push_back(i);
}
}
set<pair<int, int>> st;
for (auto [x, y] : S1) {
vector<int> v;
for (int z : G[0][2][x]) for (int z1 : G[1][2][y]) {
if (z == z1) v.push_back(f(x, y, z));
}
for (int i = 0; i < (int)v.size() - 1; i++) {
int u1 = v[i];
int u2 = v[i + 1];
gph[u1].push_back(u2);
gph[u2].push_back(u1);
st.insert({u1, u2});
st.insert({u2, u1});
}
}
for (auto [x, z] : S2) {
vector<int> v;
for (int y : G[0][1][x]) for (int y1 : G[2][1][z]) {
if (y == y1) v.push_back(f(x, y, z));
}
for (int i = 0; i < (int)v.size() - 1; i++) {
int u1 = v[i];
int u2 = v[i + 1];
gph[u1].push_back(u2);
gph[u2].push_back(u1);
st.insert({u1, u2});
st.insert({u2, u1});
}
}
for (auto [y, z] : S3) {
vector<int> v;
for (int x : G[1][0][y]) for (int x1 : G[2][0][z]) {
if (x == x1) v.push_back(f(x, y, z));
}
for (int i = 0; i < (int)v.size() - 1; i++) {
int u1 = v[i];
int u2 = v[i + 1];
gph[u1].push_back(u2);
gph[u2].push_back(u1);
st.insert({u1, u2});
st.insert({u2, u1});
}
}
n = mp.size();
int ans = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
dfs(i);
bool flag = false;
for (int x : vec)
if (gph[x].size() == 3) flag = true;
if (flag) {
assert(vec.size() <= 8);
int sz = vec.size();
int cnt = 0;
for (int j = 0; j < (1 << sz); j++) {
bool flag = true;
for (int u = 0; u < sz; u++) if (j >> u & 1) {
for (int v = 0; v < sz; v++) if (j >> v & 1)
if (st.find({vec[u], vec[v]}) != st.end()) flag = false;
}
if (flag) cnt = max(cnt, __builtin_popcount(j));
}
ans += cnt;
}
else {
bool flag = false;
for (int x : vec)
if (gph[x].size() == 1) flag = true;
if (flag) {
solve(vec[0], vec[0]);
ans += max(dp[0][vec[0]], dp[1][vec[0]]);
}
else
ans += (int)vec.size() / 2;
}
vec.clear();
}
cout << ans;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 19012kb
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: 5ms
memory: 19356kb
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...