QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187547 | #3848. Building on the Moon | ucup-team004# | TL | 607ms | 3824kb | C++20 | 3.4kb | 2023-09-24 17:59:21 | 2023-09-24 17:59:22 |
Judging History
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