QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130857#4938. Writing Taskskaruna#WA 337ms80176kbC++174.1kb2023-07-25 14:15:112023-07-25 14:15:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-25 14:15:12]
  • 评测
  • 测评结果:WA
  • 用时:337ms
  • 内存:80176kb
  • [2023-07-25 14:15:11]
  • 提交

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'