QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#619792 | #2443. Dense Subgraph | PlentyOfPenalty# | WA | 326ms | 16136kb | C++20 | 2.9kb | 2024-10-07 15:25:11 | 2024-10-07 15:25:12 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
const int N = 35010, M = 5;
const int mod = 1e9 + 7;
int T, n, u, v, a[N];
int f[N][(1 << M) + 10], g[N], t[N][2], sz[N];
int lb[(1 << M) + 10], tg[(1 << M) + 10], ans;
vector<int> e[N], s[N];
int Check(int x, int y, int z) { return a[x] + a[y] + a[z] <= 0; }
void Merge(int x, int y) {
// log("Merge %d %d\n", x, y);
t[y][0] = t[y][1] = 0;
tg[0] = 1;
for (int i = 0; i < (1 << sz[y]); ++i) {
if (i) {
tg[i] = (tg[i - (1 << lb[i])] & Check(s[y][lb[i]], y, x));
}
(t[y][0] += f[y][i]) >= mod ? t[y][0] -= mod : 0;
if (tg[i]) (t[y][1] += f[y][i]) >= mod ? t[y][1] -= mod : 0;
}
if (!Check(x, y, 0)) t[y][1] = 0;
// log("CHK %d %d=%d\n", x, y, Check(x, y, 0));
// log("T %d 0=%d,1=%d\n", y, t[y][0], t[y][1]);
}
void dfs(int x, int fa) {
// log("DFS %d\n", x);
sz[x] = 0;
for (int i : e[x])
if (i != fa) {
++sz[x];
s[x].push_back(i);
dfs(i, x);
Merge(x, i);
}
assert(0 <= sz[x] && sz[x] <= 5);
// log("SOLVE %d\n", x);
g[x] = 1;
for (int i : s[x]) {
g[x] = 1ll * g[x] * (g[i] + t[i][0]) % mod;
}
tg[0] = 1;
for (int i = 0; i < (1 << sz[x]); ++i) {
if (i) {
u = lb[i];
tg[i] = tg[i - (1 << u)];
for (int j = u + 1; j < sz[x] && tg[i]; ++j)
if (i & (1 << j)) {
tg[i] &= Check(x, s[x][u], s[x][j]);
}
}
// log("TG %d=%d\n", i, tg[i]);
f[x][i] = tg[i];
for (int j = 0; j < sz[x] && f[x][i]; ++j) {
if (i & (1 << j)) {
f[x][i] = 1ll * f[x][i] * t[s[x][j]][1] % mod;
} else {
f[x][i] = 1ll * f[x][i] * g[s[x][j]] % mod;
}
}
}
// for (int i = 0; i < (1 << sz[x]); ++i) {
// log("F %d %d=%d\n", x, i, f[x][i]);
// }
// log("G %d=%d\n", x, g[x]);
}
#define clear(a) memset(a, 0, sizeof(a))
int main() {
#ifdef memset0
// freopen("F.in", "r", stdin);
freopen("F0.txt", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> T;
for (int i = 1; i < (1 << M); ++i) lb[i] = ((i & 1) ? 0 : lb[i >> 1] + 1);
while (T--) {
clear(a);
clear(f);
clear(g);
clear(t);
clear(sz);
clear(tg);
// log("-------------------T=%d\n", T);
cin >> n >> v;
for (int i = 1; i <= n; ++i) cin >> a[i], a[i] -= v;
for (int i = 1; i <= n; ++i) {
vector<int>().swap(e[i]);
vector<int>().swap(s[i]);
}
for (int i = 1; i < n; ++i) {
cin >> u >> v;
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 0);
ans = g[1];
for (int i = 0; i < (1 << sz[1]); ++i) {
(ans += f[1][i]) >= mod ? ans -= mod : 0;
}
cout << ans << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 326ms
memory: 16136kb
input:
30 10 11086 10189 24947 2265 9138 27104 12453 15173 3048 30054 2382 8 1 1 4 5 10 10 4 3 5 2 10 9 7 6 10 7 1 15 9664 4127 24649 13571 8586 34629 8644 3157 33133 3713 32646 29412 8108 13583 21362 23735 14 9 7 1 15 12 10 15 2 6 3 11 9 1 1 11 6 12 4 10 13 15 8 15 12 11 5 3 20 29310 21738 9421 8412 4617 ...
output:
320 3312 1048576 428648761 799497565 840192586 473482800 609525844 303887775 58962594 681428379 354510769 934532981 98847637 345684331 499832606 18379714 234468663 882529214 813940859 507777499 676975680 298509209 615823216 318541589 63608091 225664347 634600456 743329186 504363306
result:
wrong answer 4th lines differ - expected: '60461799', found: '428648761'