QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187547#3848. Building on the Moonucup-team004#TL 607ms3824kbC++203.4kb2023-09-24 17:59:212023-09-24 17:59:22

Judging History

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

  • [2023-09-24 17:59:22]
  • 评测
  • 测评结果:TL
  • 用时:607ms
  • 内存:3824kb
  • [2023-09-24 17:59:21]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1000003;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, L;
    std::cin >> N >> L;

    std::vector<std::array<int, 3>> c(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> c[i][j];
            c[i][j]--;
        }
    }

    std::vector<int> f(6 * N), siz(6 * N);
    std::iota(f.begin(), f.end(), 0);

    auto find = [&](int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    };

    auto merge = [&](int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        f[x] = y;
        siz[y] += siz[x];
        return true;
    };

    for (int x = 0; x < N; x++) {
        for (int j = 0; j < 3; j++) {
            int y = c[x][j];
            if (x < y) {
                int k = 0;
                while (c[y][k] != x) {
                    k++;
                }
                merge(x * 6 + 2 * j, y * 6 + 2 * k + 1);
                merge(x * 6 + 2 * j + 1, y * 6 + 2 * k);
            }
        }
    }

    std::vector<int> id(6 * N);
    int cur = 0;
    for (int i = 0; i < 6 * N; i++) {
        if (f[i] == i) {
            id[i] = cur++;
        }
    }
    for (int i = 0; i < 6 * N; i++) {
        id[i] = id[find(i)];
    }

    const int m = N * 3;
    assert(m == cur);
    std::vector g(m, std::vector<int>(m));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 6; j++) {
            int u = id[i * 6 + j];
            int v = id[i * 6 + (j + 1) % 6];
            g[u][v] = g[v][u] = (j % 2 == 0 ? L + 1 : 1);
        }
    }

    std::vector<std::array<int, 2>> e1;
    std::vector<std::array<int, 2>> e2;

    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (g[i][j] > 1) {
                e1.push_back({i, j});
            } else if (g[i][j] == 1) {
                e2.push_back({i, j});
            }
        }
    }
    
//    std::cerr << e1.size() << " " << e2.size() << "\n";

    int ans = 0;
    std::vector<bool> vis(m);
    f.resize(m);
    std::vector<int> pw(e1.size() + 1);
    std::vector<int> p2(e2.size() + 1);
    pw[0] = 1;
    for (int i = 1; i <= e1.size(); i++) {
        pw[i] = 1LL * pw[i - 1] * (L + 1) % P;
    }
    p2[0] = 1;
    for (int i = 1; i <= e2.size(); i++) {
        p2[i] = 1LL * p2[i - 1] * 2 % P;
    }
    for (int s = 0; s < (1 << e1.size()); s++) {
        int ways = 1;
        std::iota(f.begin(), f.end(), 0);
        siz.assign(m, 1);
        vis.assign(m, false);
        int cnt = 0;
        for (int i = 0; i < e1.size(); i++) {
            if (s >> i & 1) {
                vis[e1[i][0]] = vis[e1[i][1]] = true;
                cnt++;
            }
        }
        int c2 = 0;
        for (auto [u, v] : e2) {
            if (!vis[u] && !vis[v]) {
                if (!merge(u, v)) {
                    c2++;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if (!vis[i] && f[i] == i && siz[i] % 2) {
                ways = 0;
                break;
            }
        }
        ans = (ans + 1LL * ways * pw[cnt] % P * p2[c2]) % P;
    }

    std::cout << ans << "\n";

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

4 1
2 3 4
1 4 3
1 2 4
1 3 2

output:

108

result:

ok single line: '108'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

4 20
2 3 4
1 4 3
1 2 4
1 3 2

output:

804233

result:

ok single line: '804233'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4 100
2 3 4
1 4 3
1 2 4
1 3 2

output:

117845

result:

ok single line: '117845'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

8 52
4 5 2
1 6 3
2 7 4
3 8 1
8 6 1
5 7 2
6 8 3
7 5 4

output:

986302

result:

ok single line: '986302'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

8 99
4 5 2
1 6 3
2 7 4
3 8 1
8 6 1
5 7 2
6 8 3
7 5 4

output:

25

result:

ok single line: '25'

Test #6:

score: 0
Accepted
time: 601ms
memory: 3568kb

input:

14 43
7 8 2
1 9 3
2 10 4
3 11 5
4 12 6
5 13 7
6 14 1
14 9 1
8 10 2
9 11 3
10 12 4
11 13 5
12 14 6
13 8 7

output:

426592

result:

ok single line: '426592'

Test #7:

score: 0
Accepted
time: 603ms
memory: 3632kb

input:

14 77
7 8 2
1 9 3
2 10 4
3 11 5
4 12 6
5 13 7
6 14 1
14 9 1
8 10 2
9 11 3
10 12 4
11 13 5
12 14 6
13 8 7

output:

267434

result:

ok single line: '267434'

Test #8:

score: 0
Accepted
time: 599ms
memory: 3572kb

input:

14 23
2 3 4
1 5 3
1 2 6
1 6 7
2 8 9
3 10 4
4 11 12
5 13 9
5 8 10
6 9 14
7 14 12
7 11 13
8 12 14
10 13 11

output:

843062

result:

ok single line: '843062'

Test #9:

score: 0
Accepted
time: 594ms
memory: 3780kb

input:

14 87
2 3 4
1 5 3
1 2 6
1 6 7
2 8 9
3 10 4
4 11 12
5 13 9
5 8 10
6 9 14
7 14 12
7 11 13
8 12 14
10 13 11

output:

315869

result:

ok single line: '315869'

Test #10:

score: 0
Accepted
time: 595ms
memory: 3568kb

input:

14 46
2 3 4
1 5 3
1 2 6
1 6 7
2 8 9
3 10 4
4 11 12
5 13 9
5 8 10
6 9 14
7 14 12
7 11 13
8 12 14
10 13 11

output:

424598

result:

ok single line: '424598'

Test #11:

score: 0
Accepted
time: 605ms
memory: 3568kb

input:

14 24
2 3 4
1 5 6
1 7 8
1 9 10
2 11 12
2 13 14
3 14 12
3 11 9
4 8 10
4 9 11
5 10 8
5 7 13
6 12 14
6 13 7

output:

426600

result:

ok single line: '426600'

Test #12:

score: 0
Accepted
time: 599ms
memory: 3604kb

input:

14 59
2 3 4
1 5 6
1 7 8
1 9 10
2 11 12
2 13 14
3 14 12
3 11 9
4 8 10
4 9 11
5 10 8
5 7 13
6 12 14
6 13 7

output:

174886

result:

ok single line: '174886'

Test #13:

score: 0
Accepted
time: 602ms
memory: 3824kb

input:

14 92
2 3 4
1 5 6
1 7 8
1 9 10
2 11 12
2 13 14
3 14 12
3 11 9
4 8 10
4 9 11
5 10 8
5 7 13
6 12 14
6 13 7

output:

651944

result:

ok single line: '651944'

Test #14:

score: 0
Accepted
time: 601ms
memory: 3776kb

input:

14 89
2 3 4
1 5 6
1 7 8
1 9 10
2 11 6
2 5 7
3 6 8
3 7 12
4 13 10
4 9 11
5 10 14
8 14 13
9 12 14
11 13 12

output:

6992

result:

ok single line: '6992'

Test #15:

score: 0
Accepted
time: 602ms
memory: 3568kb

input:

14 37
2 3 4
1 5 6
1 7 8
1 9 10
2 11 6
2 5 7
3 6 8
3 7 12
4 13 10
4 9 11
5 10 14
8 14 13
9 12 14
11 13 12

output:

375845

result:

ok single line: '375845'

Test #16:

score: 0
Accepted
time: 605ms
memory: 3776kb

input:

14 76
2 3 4
1 5 6
1 7 8
1 9 10
2 11 6
2 5 7
3 6 8
3 7 12
4 13 10
4 9 11
5 10 14
8 14 13
9 12 14
11 13 12

output:

931940

result:

ok single line: '931940'

Test #17:

score: 0
Accepted
time: 605ms
memory: 3628kb

input:

14 77
2 3 4
1 5 6
1 7 8
1 9 5
2 4 10
2 11 7
3 6 11
3 12 9
4 8 13
5 14 11
6 10 7
8 14 13
9 12 14
10 13 12

output:

648150

result:

ok single line: '648150'

Test #18:

score: 0
Accepted
time: 607ms
memory: 3564kb

input:

14 60
2 3 4
1 5 6
1 7 8
1 9 5
2 4 10
2 11 7
3 6 11
3 12 9
4 8 13
5 14 11
6 10 7
8 14 13
9 12 14
10 13 12

output:

156164

result:

ok single line: '156164'

Test #19:

score: 0
Accepted
time: 602ms
memory: 3640kb

input:

14 1
2 3 4
1 5 6
1 7 8
1 9 5
2 4 10
2 11 7
3 6 11
3 12 9
4 8 13
5 14 11
6 10 7
8 14 13
9 12 14
10 13 12

output:

188581

result:

ok single line: '188581'

Test #20:

score: -100
Time Limit Exceeded

input:

16 1
2 3 4
1 6 5
1 9 12
1 13 16
2 7 8
8 7 2
8 5 6
5 7 6
10 11 3
9 12 11
9 10 12
3 11 10
14 15 4
16 15 13
13 14 16
4 15 14

output:


result: