QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#145280#6742. Leavesberarchegas#RE 1ms3800kbC++172.4kb2023-08-22 02:47:142023-08-22 02:47:16

Judging History

你现在查看的是最新测评结果

  • [2023-08-22 02:47:16]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3800kb
  • [2023-08-22 02:47:14]
  • 提交

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

output:


result: