QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130857 | #4938. Writing Tasks | karuna# | WA | 337ms | 80176kb | C++17 | 4.1kb | 2023-07-25 14:15:11 | 2023-07-25 14:15:12 |
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}];
}
int col[MAXN];
vector<int> gph[MAXN];
void dfs(int v, int z) {
if (col[v]) {
assert(col[v] == z);
return;
}
col[v] = z;
for (int x : gph[v]) {
dfs(x, z ^ 3);
}
}
struct edge {
int u, v, c, dual;
};
vector<edge> adj[MAXN];
void add_edge(int u, int v) {
adj[u].push_back({u, v, 1, (int)adj[v].size()});
adj[v].push_back({v, u, 0, (int)adj[u].size() - 1});
}
int dist[MAXN];
int sp[MAXN];
int flow(int v, int minf) {
if (v == snk) return minf;
while (sp[v] < adj[v].size()) {
auto &e = adj[v][sp[v]++];
if (e.c == 0 || dist[e.v] != dist[v] + 1) continue;
int f = flow(e.v, min(minf, e.c));
if (f != 0) {
e.c -= f;
adj[e.v][e.dual].c += f;
return f;
}
}
return 0;
}
int run() {
for (int i = 0; i <= n + 2; i++) dist[i] = 1e9;
queue<int> q;
q.push(src);
dist[src] = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto e : adj[v]) if (e.c > 0) {
if (dist[e.v] == 1e9) {
dist[e.v] = dist[v] + 1;
q.push(e.v);
}
}
}
int res = 0;
int f = flow(src, 1e9);
while (f > 0) {
res += f;
f = flow(src, 1e9);
}
return res;
}
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);
}
}
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);
}
}
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);
}
}
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);
}
}
n = mp.size();
for (int i = 1; i <= n; i++) if (!col[i]) dfs(i, 1);
src = n + 1;
snk = n + 2;
for (int i = 1; i <= n; i++) {
if (col[i] == 1) {
add_edge(src, i);
for (int x : gph[i]) add_edge(i, x);
}
else add_edge(i, snk);
}
int ans = 0;
int f = run();
while (f > 0) {
ans += f;
f = run();
}
cout << n - ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 24856kb
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: 25120kb
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: 260ms
memory: 74512kb
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: 276ms
memory: 74504kb
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: 337ms
memory: 80176kb
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: 7ms
memory: 24628kb
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: 0ms
memory: 24440kb
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: 2ms
memory: 26432kb
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: 103ms
memory: 45908kb
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: 1ms
memory: 25112kb
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: 2ms
memory: 25300kb
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: 2ms
memory: 25840kb
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: 0ms
memory: 24928kb
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: 107ms
memory: 47456kb
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: 3ms
memory: 24840kb
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: 1ms
memory: 24400kb
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: 7ms
memory: 25552kb
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: 106ms
memory: 47228kb
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: 0ms
memory: 24764kb
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: 2ms
memory: 24512kb
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: -100
Wrong Answer
time: 99ms
memory: 45612kb
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:
32562
result:
wrong answer 1st lines differ - expected: '28939', found: '32562'