QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#145280 | #6742. Leaves | berarchegas# | RE | 1ms | 3800kb | C++17 | 2.4kb | 2023-08-22 02:47:14 | 2023-08-22 02:47:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int MAXN = 1e3 + 5;
const ll INF = 2e18;
int val[MAXN], rotulo[MAXN], qtd[MAXN], l[MAXN], r[MAXN];
set<int> folhas[MAXN], lefty[MAXN], righty[MAXN];
void calc(int node, int p = 0, bool plus = false) {
qtd[node] = qtd[p] + plus;
if (l[node]) {
calc(l[node], node, false);
calc(r[node], node, true);
for (int x : folhas[l[node]]) {
folhas[node].insert(x);
lefty[node].insert(x);
}
for (int x : folhas[r[node]]) {
folhas[node].insert(x);
righty[node].insert(x);
}
}
else {
folhas[node].insert(val[node]);
}
}
int dfs(int node, int operations, int meta = 0) {
// cout << node << " =\n";
int have = operations;
if (val[node]) {
cout << val[node] << ' ';
return have;
}
if (meta) {
if (lefty[node].count(val[meta])) {
have = dfs(l[node], have, meta);
have = dfs(r[node], have);
}
else {
have = dfs(r[node], have, meta);
have = dfs(l[node], have);
}
return have;
}
for (int x : folhas[node]) {
// cout << x << ": " << qtd[rotulo[x]] - qtd[node] << '\n';
if (qtd[rotulo[x]] - qtd[node] <= operations) {
if (lefty[node].count(x)) {
have = dfs(l[node], have - qtd[rotulo[x]] + qtd[node], rotulo[x]);
have = dfs(r[node], have);
}
else {
have = dfs(r[node], have - qtd[rotulo[x]] + qtd[node], rotulo[x]);
have = dfs(l[node], have);
}
return have;
}
}
return have;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
int tipo, a, b;
for (int i = 1; i <= n; i++) {
cin >> tipo;
if (tipo == 1) {
cin >> a >> b;
l[i] = a;
r[i] = b;
}
else {
cin >> val[i];
rotulo[val[i]] = i;
}
}
calc(1);
dfs(1, m);
cout << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
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: 3800kb
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: 3712kb
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: -100
Runtime Error
input:
1 0 2 1000000000