QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413601 | #6742. Leaves | HHY_zZhu# | WA | 1ms | 3836kb | C++20 | 4.3kb | 2024-05-17 19:44:17 | 2024-05-17 19:44:18 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int INF = 1e9 + 7;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
std::vector<std::pair<int, int>> son(n);
std::vector<uint8_t> has_father(n);
for (int i = 0; i < n; ++i) {
int tp;
std::cin >> tp;
if (tp == 1) {
int l, r;
std::cin >> l >> r;
--l, --r;
son[i] = {l, r};
has_father[l] = has_father[r] = true;
} else {
std::cin >> a[i];
}
}
int rt = 0;
while (has_father[rt]) {
++rt;
}
auto concatenate = [](std::vector<int> a, std::vector<int> b) {
a.insert(a.end(), b.begin(), b.end());
return a;
};
struct Node {
std::vector<int> arr;
int m;
bool f;
};
std::vector<Node> dp(n);
std::vector<int> sz(n);
std::vector<std::vector<int>> origin(n);
auto dfs0 = [&](auto self, int node) -> void {
if (son[node].first == son[node].second) {
sz[node] = 1;
dp[node].arr = std::vector<int>{a[node]};
dp[node].m = 0;
dp[node].f = false;
origin[node] = std::vector<int>{a[node]};
return;
}
auto [l, r] = son[node];
self(self, l);
self(self, r);
sz[node] = sz[l] + sz[r];
origin[node] = concatenate(origin[l], origin[r]);
std::vector<int> l_first = concatenate(dp[l].arr, dp[r].arr);
std::vector<int> r_first = concatenate(dp[r].arr, dp[l].arr);
if (l_first == r_first) {
dp[node].arr = std::move(l_first);
dp[node].m = dp[l].m + dp[r].m;
dp[node].f = true;
} else if (l_first < r_first) {
dp[node].arr = std::move(l_first);
dp[node].m = dp[l].m + dp[r].m;
dp[node].f = false;
} else {
dp[node].arr = std::move(r_first);
dp[node].m = dp[l].m + dp[r].m + 1;
dp[node].f = false;
}
};
dfs0(dfs0, rt);
auto check = [](const std::vector<int> &v, auto it) -> bool {
for (int i = 0; i < v.size(); ++i) {
if (v[i] > it[i]) {
return false;
}
}
return true;
};
auto solve = [&](auto self, int node, int m, bool f, auto it) -> std::vector<int> {
if (m == 0) {
return origin[node];
}
if (son[node].first == son[node].second) {
if (m % 2 == 0 || f) {
return std::vector<int>{a[node]};
} else {
return std::vector<int>{INF};
}
}
auto [l, r] = son[node];
std::vector<int> ans(it, it + sz[node]);
bool flag = false;
// Not change
{
std::vector<int> res(sz[node], INF);
if (m <= dp[l].m) {
res = concatenate(self(self, l, m, f, ans.begin()), origin[r]);
} else if (check(dp[l].arr, ans.begin())) {
res = concatenate(dp[l].arr, self(self, r, m - dp[l].m, f || dp[l].f, res.begin() + sz[l]));
}
if (std::find(res.begin(), res.end(), INF) == res.end() && res <= ans) {
ans = res;
flag = true;
}
}
// Change
{
m -= 1;
std::vector<int> res(sz[node], INF);
if (m <= dp[r].m) {
res = concatenate(self(self, r, m, f, ans.begin()), origin[l]);
} else if (check(dp[r].arr, ans.begin())) {
res = concatenate(dp[r].arr, self(self, l, m - dp[r].m, f || dp[r].f, res.begin() + sz[r]));
}
if (std::find(res.begin(), res.end(), INF) == res.end() && res <= ans) {
ans = res;
flag = true;
}
}
if (flag) {
return ans;
} else {
return std::vector<int>(sz[node], INF);
}
};
std::vector<int> ans(sz[rt], INF);
ans = solve(solve, rt, m, false, ans.begin());
for (int i : ans) {
std::cout << i << ' ';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
input:
3 0 1 2 3 2 1 2 2
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
7 1 1 2 3 1 4 5 1 6 7 2 4 2 2 2 3 2 1
output:
2 4 3 1
result:
ok 4 number(s): "2 4 3 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
7 2 1 2 3 1 4 5 1 6 7 2 4 2 2 2 3 2 1
output:
1 3 4 2
result:
ok 4 number(s): "1 3 4 2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
1 0 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
3 1 1 2 3 2 1 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
7 2 1 2 3 1 4 5 1 6 7 2 1 2 2 2 3 2 4
output:
1 2 3 4
result:
ok 4 number(s): "1 2 3 4"
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3812kb
input:
999 480 1 3 2 1 4 5 1 6 7 1 9 8 1 10 11 1 13 12 1 14 15 1 16 17 1 19 18 1 21 20 1 23 22 1 25 24 1 27 26 1 28 29 1 30 31 1 33 32 1 35 34 1 37 36 1 38 39 1 41 40 1 42 43 1 45 44 1 46 47 1 48 49 1 51 50 1 52 53 1 55 54 1 56 57 1 58 59 1 61 60 1 62 63 1 64 65 1 67 66 1 69 68 1 71 70 1 73 72 1 74 75 1 76...
output:
125712955 763875883 763875883 763875883 763875883 763875883 763875883 763875883 277558689 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 ...
result:
wrong answer 1st numbers differ - expected: '34826804', found: '125712955'