QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588176#5437. Graph Completingucup-team2526WA 2ms8264kbC++173.4kb2024-09-25 05:08:372024-09-25 05:08:38

Judging History

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

  • [2024-09-25 05:08:38]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：8264kb
查看
  • [2024-09-25 05:08:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 7005, MAXM = 40005, P = 998244353;
int qpow(int a, long long b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return ans;
}
int n, m;
int pn;
int u[MAXM], v[MAXM];
#define forGraph(u, v) for (int i = fst[u], v = to[i]; i; i = nxt[i], v = to[i])
int f[MAXN][MAXN], g[MAXN][MAXN];
int Pow2[MAXN], PPow2[MAXN];
int pow2(long long b) {
    return 1ll * Pow2[b % n] * PPow2[b / n] % P;
}
struct Tree {
    int fst[MAXN], to[MAXM << 1], nxt[MAXM << 1], tot;
    int siz[MAXN], cnt[MAXN], n;
    int bl[MAXN];
    void add(int u, int v) {
        to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot;
    }
    void dfs(int u, int pre) {
        f[u][siz[u]] = qpow(2, 1ll * siz[u] * (siz[u] - 1) / 2 - cnt[u]);
if (pn==200)cout << u << ' ' << f[u][siz[u]];
        forGraph(u, v) if (v != pre) {
            dfs(v, u);
            for (int i = 0; i <= siz[u] + siz[v]; i++) {
                g[u][i] = 0;
            }
            for (int i = 0; i <= siz[u]; i++) if (f[u][i]) {
                for (int j = 0; j <= siz[v]; j++) if (f[v][j]) {
                    g[u][i + j] = (g[u][i + j] + 1ll * f[u][i] * f[v][j] % P * 
                        // qpow(2, 1ll * i * j - 1)
                        pow2(1ll * i * j - 1)
                        ) % P;
                    g[u][i] = (g[u][i] - 1ll * f[u][i] * f[v][j] % P + P) % P;
                }
            }
            for (int i = 0; i <= siz[u] + siz[v]; i++) {
                f[u][i] = g[u][i];
            }
            siz[u] += siz[v];
        }
    }
} t;
int test;
struct Graph {
    int fst[MAXN], to[MAXM << 1], nxt[MAXM << 1], tot;
    Graph() : tot(1) {}
    void add(int u, int v) {
        to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot;
    }
    int dfn[MAXN], low[MAXN], dcnt;
    bool vis[MAXM << 1];
    void tarjan(int u, int inEdge) {
        dfn[u] = low[u] = ++dcnt;
        forGraph(u, v) if (!dfn[v]) {
            tarjan(v, i ^ 1);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                test++;
                vis[i] = vis[i ^ 1] = 1;
            }
        } else if (i != inEdge) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    void dfs(int u, int id) {
        t.bl[u] = id;
        t.siz[id]++;
        forGraph(u, v) if (!vis[i] && !t.bl[v]) {
            dfs(v, id);
        }
    }
} G;
int main() {
    scanf("%d%d", &n, &m);
pn= n;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u[i], &v[i]);
        G.add(u[i], v[i]);
        G.add(v[i], u[i]);
    }
    Pow2[0] = PPow2[0] = 1;
    for (int i = 1; i <= n; i++) {
        Pow2[i] = 2ll * Pow2[i - 1] % P;
    }
    for (int i = 1; i <= n; i++) {
        PPow2[i] = 1ll * PPow2[i - 1] * Pow2[n] % P;
    }
    G.tarjan(1, 0);
    for (int i = 1; i <= n; i++) if (!t.bl[i]) {
        int id = ++t.n;
        G.dfs(i, id);
    }
    for (int i = 1; i <= m; i++) {
        if (t.bl[u[i]] == t.bl[v[i]]) {
            t.cnt[t.bl[u[i]]]++;
        } else {
            t.add(t.bl[u[i]], t.bl[v[i]]);
            t.add(t.bl[v[i]], t.bl[u[i]]);
        }
    }
    t.dfs(1, 0);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + f[1][i]) % P;
    }
    printf("%d\n", ans);
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8012kb

input:

3 2
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

4 4
1 2
2 3
3 4
4 1

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

2 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

3 3
1 2
2 3
3 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

4 3
1 2
2 3
3 4

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

4 3
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #7:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #8:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

141 9870
124 111
31 87
121 106
127 90
54 125
38 17
115 23
129 111
8 116
90 85
10 29
96 110
24 125
51 113
119 33
58 64
8 5
54 97
112 44
70 138
116 85
38 138
138 21
26 18
69 128
68 31
69 42
126 110
49 118
83 124
69 4
9 110
88 104
48 53
46 30
111 120
99 85
13 85
73 85
40 124
39 38
121 40
46 100
29 61
4...

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 2ms
memory: 8160kb

input:

142 10000
19 3
4 86
36 122
36 88
130 86
107 59
3 119
132 90
80 124
122 95
75 66
70 123
63 119
8 44
114 9
81 19
106 77
96 93
79 141
104 50
117 66
30 48
128 109
56 73
106 116
70 8
72 130
59 110
140 20
40 11
134 71
27 51
33 93
82 96
133 118
50 14
32 64
71 12
48 33
22 32
116 17
104 45
66 71
111 142
131 ...

output:

2048

result:

ok 1 number(s): "2048"

Test #11:

score: -100
Wrong Answer
time: 2ms
memory: 8264kb

input:

200 10000
47 42
33 120
146 144
94 170
170 181
20 101
185 190
197 33
18 37
12 86
148 115
136 120
41 182
120 11
44 132
167 67
118 139
114 52
80 37
171 56
93 139
113 112
129 122
166 4
47 60
57 6
104 119
179 104
107 1
8 70
197 70
39 127
134 1
18 26
85 100
158 121
61 105
33 113
51 54
45 85
45 130
97 164
...

output:

1 365281854365281854

result:

wrong answer 1st numbers differ - expected: '365281854', found: '1'
English 繁體中文 简体中文

Server Time: 2024-12-02 19:02:43 | OpenSource Project