NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 4	3ms	404 KiB
#2	Accepted 4	2ms	404 KiB
#3	Accepted 4	2ms	404 KiB
#4	Accepted 4	41ms	420 KiB
#5	Accepted 4	4ms	404 KiB
#6	Accepted 4	3ms	404 KiB
#7	Wrong Answer 0 读取到 425781253，应为 101128313。	2ms	316 KiB
#8	Wrong Answer 0 读取到 425781253，应为 864847290。	2ms	404 KiB
#9	Wrong Answer 0 读取到 981689460，应为 316370895。	6ms	404 KiB
#10	Wrong Answer 0 读取到 981689460，应为 216694257。	6ms	404 KiB
#11	Wrong Answer 0 读取到 981689460，应为 489379228。	6ms	408 KiB
#12	Wrong Answer 0 读取到 129333497，应为 733892377。	26ms	428 KiB
#13	Wrong Answer 0 读取到 129333497，应为 659402421。	26ms	416 KiB
#14	Wrong Answer 0 读取到 535644535，应为 173351237。	55ms	408 KiB
#15	Wrong Answer 0 读取到 535644535，应为 809770418。	59ms	424 KiB
#16	Wrong Answer 0 读取到 535644535，应为 34568451。	61ms	428 KiB
#17	Wrong Answer 0 读取到 425781253，应为 834878291。	2ms	404 KiB
#18	Wrong Answer 0 读取到 425781253，应为 684333880。	2ms	404 KiB
#19	Wrong Answer 0 读取到 981689460，应为 317225586。	6ms	408 KiB
#20	Wrong Answer 0 读取到 981689460，应为 451649718。	6ms	404 KiB
#21	Wrong Answer 0 读取到 129333497，应为 220986747。	27ms	424 KiB
#22	Wrong Answer 0 读取到 129333497，应为 14285111。	26ms	432 KiB
#23	Wrong Answer 0 读取到 129333497，应为 580901699。	27ms	420 KiB
#24	Wrong Answer 0 读取到 535644535，应为 380460596。	56ms	424 KiB
#25	Wrong Answer 0 读取到 535644535，应为 171458070。	56ms	404 KiB

#include <bits/stdc++.h>

using namespace std;

const int N = 50, P = 1e9 + 7, I2 = (P + 1) >> 1;

// namespace solver {
//     int G[N], f[1 << N], g[1 << N];

//     void solve(int n, vector< array<int, 3> > E) {
//         for (int i = 0; i < n; ++i) G[i] = 0;
//         for (auto it : E) {
//             G[it[1]] |= (1 << it[2]);
//             G[it[2]] |= (1 << it[1]);
//         }
//         for (int i = 0; i < (1 << n); ++i) f[i] = g[i] = 0;
//         for (int i = 1; i < (1 << n); ++i) {
//             f[i] = 1, g[i] = 0;
//             int t = __builtin_ctz(i);
//             for (int j = (i - 1) & i; j; j = (j - 1) & i) {
//                 if (!(j >> t) & 1) continue;
//                 f[i] = (f[i] - 1ll * (f[j] + g[j]) * pw[cnt + cnt] % P) % P;
//                 g[i] = (g[i] - 1ll * (f[j] + g[j]) * pw[cnt + cnt] % P) % P;
//             }
//             f[i] = (f[i] - g[i] + P) % P;
//         }
//         printf("%d\n", (f[(1 << n) - 1] + g[(1 << n) - 1])) % P;
//     }
// }

vector<int> G[N];
int fa[N], ok[1 << 20], vis[N];

int find(int x) {
    return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void Dfs(int x) {
    vis[x] = 1;
    for (auto v : G[x]) {
        if (!vis[v]) Dfs(v);
    }
}

vector< pair<int, int> > G2[N];
int hv[N];

void dfs(int x, int fa = -1) {
    for (auto it : G2[x]) {
        int v = it.first, w = it.second;
        if (v == fa) continue;
        hv[w] = 1;
        dfs(v, x);
    }
}

signed main() {
    freopen("years.in", "r", stdin);
    freopen("years.out", "w", stdout);
    int T; scanf("%*d%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        vector< array<int, 3> > E;
        map<int, int> M;
        int flgg = 1;
        for (int i = 1, x, y, w; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &w), --x, --y;
            E.push_back({w, x, y});
            flgg &= !M[w]++;
        }
        sort(E.begin(), E.end());
        if (n <= 6 && m <= 6) {
            iota(fa, fa + n, 0);
            int sum = 0;
            for (auto it : E) {
                if (find(it[1]) == find(it[2])) continue;
                fa[find(it[1])] = find(it[2]);
                sum += it[0];
            }
            for (int i = 0; i < (1 << (m * 2)); ++i) {
                int S = 0;
                for (int j = 0; j < m; ++j) {
                    if ((i >> (j * 2)) & 1) S += E[j][0];
                    if ((i >> (j * 2 + 1)) & 1) S += E[j][0];
                }
                ok[i] = 0;
                if (S != sum) continue;
                for (int j = 0; j < n; ++j) G[j].clear();
                for (int j = 0; j < m; ++j) {
                    if ((i >> (j * 2)) & 1) {
                        G[E[j][1]].push_back(E[j][2]);
                    }
                    if ((i >> (j * 2 + 1)) & 1) {
                        G[E[j][2]].push_back(E[j][1]);
                    }
                }
                int flg = 0;
                for (int j = 0; j < n; ++j) {
                    for (int k = 0; k < n; ++k) vis[k] = 0;
                    Dfs(j);
                    if (!count(vis, vis + n, 0)) flg = 1;
                }
                if (flg) ok[i] = 1;
            }
            int res = 0;
            for (int i = 0; i < (1 << (m + m)); ++i) {
                for (int j = 0; j < m + m; ++j) {
                    ok[i] |= ok[i & ~(1 << j)];
                }
                res += ok[i];
            }
            for (int i = 0; i < m + m; ++i) {
                res = 1ll * res * I2 % P;
            }
            printf("%d\n", res);
            continue;
        }
        if (1 || flgg) {
            iota(fa, fa + n, 0);
            for (int i = 0; i < n; ++i) G2[i].clear();
            int id = 0;
            for (auto it : E) {
                if (find(it[1]) == find(it[2])) continue;
                G2[it[1]].push_back({it[2], id++});
                G2[it[2]].push_back({it[1], id++});
                fa[find(it[1])] = find(it[2]);
            }
            int res = 0;
            for (int i = 1; i < (1 << n); ++i) {
                for (int j = 0; j < id; ++j) {
                    hv[j] = 0;
                }
                for (int j = 0; j < n; ++j) {
                    if ((i >> j) & 1) dfs(j);
                }
                int ct = 1;
                for (int j = 0; j < id; ++j) {
                    if (hv[j]) ct = 1ll * ct * I2 % P;
                }
                if (!(__builtin_popcount(i) & 1)) ct = P - ct;
                res = (res + ct) % P;
            }
            printf("%d\n", res);
            continue;
        }
        // solver::solve(n, E);
    }
    return 0;
}

递交者: FJ-SX0010
题目: NOISX2025GFE NOISX2025GFE
比赛: 【官方数据 FJ】联合省选 2025 批量测试
语言: C++14(O2)
代码长度: 4.5 KiB
递交时间: 2025-3-6 13:05:52
评测时间: 2025-3-6 16:31:32

分数: 24
总耗时: 510ms
峰值时间: 61ms
峰值内存: 432 KiB

24 Wrong Answer

代码

信息

还没有账户？

登录