QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130859 | #4938. Writing Tasks | karuna# | WA | 582ms | 79936kb | C++17 | 4.1kb | 2023-07-25 14:25:58 | 2023-07-25 14:26:02 |
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);
}
}
}
for (int i = 0; i <= n + 2; i++) sp[i] = 0;
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: 25784kb
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: 25668kb
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: 286ms
memory: 74140kb
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: 304ms
memory: 74508kb
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: 330ms
memory: 79936kb
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: 1ms
memory: 24428kb
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: 3ms
memory: 25020kb
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: 3ms
memory: 24832kb
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: 102ms
memory: 45516kb
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: 0ms
memory: 24408kb
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: 1ms
memory: 24476kb
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: 1ms
memory: 26020kb
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: 1ms
memory: 25612kb
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: 126ms
memory: 46760kb
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: 2ms
memory: 25272kb
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: 24524kb
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: 3ms
memory: 25352kb
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: 123ms
memory: 48248kb
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: 2ms
memory: 24828kb
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: 3ms
memory: 24600kb
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: 173ms
memory: 46096kb
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: 2ms
memory: 24548kb
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: 3ms
memory: 25360kb
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: 75ms
memory: 44604kb
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: 196ms
memory: 70608kb
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: 11ms
memory: 26556kb
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: 582ms
memory: 64972kb
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: 25648kb
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: 485ms
memory: 63448kb
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: 7ms
memory: 25148kb
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: 529ms
memory: 63432kb
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: -100
Wrong Answer
time: 1ms
memory: 25828kb
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:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'