QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #79753 | #5437. Graph Completing | APJifengc | WA | 3ms | 5836kb | C++14 | 3.2kb | 2023-02-20 20:50:43 | 2023-02-20 20:50:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, MAXM = 10005, 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 u[MAXN], v[MAXN];
#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];
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]);
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)) % 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;
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;
stack<int> st;
void tarjan(int u, int inEdge) {
dfn[u] = low[u] = ++dcnt;
st.push(u);
forGraph(u, v) if (!dfn[v]) {
tarjan(v, i ^ 1);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
int id = ++t.n;
while (st.top() != u) {
int w = st.top(); st.pop();
t.bl[w] = id;
t.siz[id]++;
}
}
} else if (i != inEdge) {
low[u] = min(low[u], dfn[v]);
}
if (u == 1) {
int id = ++t.n;
while (!st.empty()) {
int w = st.top(); st.pop();
t.bl[w] = id;
t.siz[id]++;
}
}
}
} G;
int main() {
scanf("%d%d", &n, &m);
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]);
}
G.tarjan(1, 0);
// printf("n = %d\n", t.n);
// for (int i = 1; i <= n; i++) {
// printf("bl[%d]=%d\n", i, t.bl[i]);
// }
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5692kb
input:
3 2 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5704kb
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: 2ms
memory: 5764kb
input:
2 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 3ms
memory: 5624kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 3ms
memory: 5644kb
input:
4 3 1 2 2 3 3 4
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5700kb
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: 5836kb
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: 1ms
memory: 5832kb
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: -100
Wrong Answer
time: 3ms
memory: 5828kb
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:
753269315
result:
wrong answer 1st numbers differ - expected: '1', found: '753269315'