QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413601#6742. LeavesHHY_zZhu#WA 1ms3836kbC++204.3kb2024-05-17 19:44:172024-05-17 19:44:18

Judging History

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

  • [2024-05-17 19:44:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2024-05-17 19:44:17]
  • 提交

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'