QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #787197 | #9806. Growing Tree | LGyxj | WA | 3ms | 4040kb | C++20 | 2.9kb | 2024-11-27 10:22:17 | 2024-11-27 10:22:18 |
Judging History
answer
//////////////////////////
// Author: lnyxj
// Time: 2024-11-27 09:23:56
///////////////////////////
#include <bits/stdc++.h>
#define xx first
#define yy second
// #define int long long
// #define double long double
using namespace std;
const int N = 2048 + 5, mod = 998244353, inv2 = mod + 1 >> 1, inf = 0x3f3f3f3f;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef long long ll;
int n, m;
int a[N], dep[N];
// vector<int> cur[N];
unordered_set<int> sts[N];
// bool cmp(int x, int lev) {
// const int t = 1 << cur[x].size();
// // const int l = x << n - lev, r = (x + 1 << n - lev) - 1;
// for (int i = 0; i < t; ++ i) {
// static bool vis[N];
// for (int k = 0; k < cur[x].size(); ++ k)
// if (i >> k & 1) vis[cur[x][k] << 1] = 1;
// else vis[cur[x][k] << 1 | 1] = 1;
// unordered_set<int> st;
// function<bool(int)> dfs = [&](int x) -> bool {
// if (x >= m || vis[x]) return true;
// if (x >= (1 << n)) {
// if (st.count(dep[x])) return false;
// st.insert(dep[x]);
// }
// return dfs(x << 1) && dfs(x << 1 | 1);
// };
// for (int k = 0; k < cur[x].size(); ++ k)
// if (i >> k & 1) vis[cur[x][k] << 1] = 0;
// else vis[cur[x][k] << 1 | 1] = 0;
// if (dfs(x)) return true;
// }
// return false;
// }
int solve(int lev, int cnt) {
if (lev == 0) return cnt - 1;
const int l = 1 << lev, r = (1 << lev + 1) - 1;
vector<int> mot;
for (int i = l; i <= r; i += 2) {
unordered_set<int> st;
int fl = 0;
for (int a : sts[i]) st.insert(a);
for (int a : sts[i + 1]) {
if (st.count(a)) {
fl = 1;
break;
}
st.insert(a);
}
if (fl) {
-- cnt;
mot.push_back(i >> 1);
} else {
sts[i >> 1].swap(st);
}
}
if (cnt < 0) return n + 1;
const int t = 1 << mot.size();
int res = n + 1;
for (int i = 0; i < t; ++ i) {
for (int j = 0; j < mot.size(); ++ j) {
const int nd = mot[j];
sts[nd].swap(sts[nd << 1 | (i >> j & 1)]);
}
res = min(res, solve(lev - 1, cnt + 1));
for (int j = 0; j < mot.size(); ++ j) {
const int nd = mot[j];
sts[nd].swap(sts[nd << 1 | (i >> j & 1)]);
}
}
return res;
// for (int i = l; i <= r; i += 2) {
// for (int a : cur[i]) cur[i >> 1].push_back(a);
// for (int a : cur[i + 1]) cur[i >> 1].push_back(a);
// if (!cmp(i >> 1, lev - 1)) cur[i >> 1].push_back(i >> 1), -- cnt;
// }
// if (cnt < 0) return n + 1;
// return solve(lev - 1, cnt + 1);
}
void solve() {
cin >> n;
m = 1 << n + 1;
for (int i = 2; i < m; ++ i)
cin >> a[i], dep[i] = dep[i >> 1] + a[i];
const int l = 1 << n;
for (int i = 1; i < l; ++ i) sts[i].clear();
for (int i = l; i < m; ++ i) sts[i].insert(dep[i]);
cout << n - solve(n, 1) << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
input:
3 2 1 2 4 3 2 1 2 1 2 3 3 2 1 2 1 2 3 3 1 1
output:
1 2 -1
result:
ok 3 number(s): "1 2 -1"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 4040kb
input:
94 5 44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2 3 83 3 74 14 45 17 22 41 62 74 25 1 56 22 7 21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...
output:
3 -1 -1 -1 0 -1 -1 0 0 -1 0 0 0 2 -1 -1 0 -1 -1 -1 0 -1 0 -1 0 0 -1 -1 -1 -1 -1 5 -1 0 4 4 -1 -1 -1 -1 2 2 -1 0 0 -1 -1 1 -1 0 -1 2 -1 0 0 0 -1 1 -1 -1 0 0 1 1 -1 0 1 5 3 -1 0 0 1 1 -1 0 -1 0 0 0 -1 3 -1 1 -1 0 0 0 0 1 1 -1 -1 -1
result:
wrong answer 1st numbers differ - expected: '2', found: '3'