oj.uz

Submission #841440

# Submission time Handle Problem Language Result Execution time Memory
841440 2023-09-01T15:40:14 Z model_code Beech Tree (IOI23_beechtree) C++17
0 / 100
 1 ms 412 KB 
// incorrect/sol_na_wa3.cpp

#include "beechtree.h"
#include <algorithm>
#include <iostream>
#include <map>

#define xx first
#define yy second

#define all(x) (x).begin(), (x).end()

std::vector<std::vector<std::pair<int, int>>> adj;

struct data
{
    bool ok = true;
    int sz = 0;
    std::map<int, int> cnt;

    data() {}

    data(int ind)
    {
        for (auto i : adj[ind])
        {
            sz++;
            cnt[i.yy]++;
            ok &= cnt[i.yy] == 1;
        }
    }

    void check(const data &masik, bool root = false)
    {
        int sum = 0;
        for (auto i : masik.cnt)
        {
            if (!root)
                ok &= i.yy <= cnt[i.xx];
            else
            {
                sum += cnt[i.xx];
            }
        }

        if (root)
            ok &= sum == sz;
    }

    void add(const data &masik, bool root = false)
    {
        ok &= masik.ok;
        for (auto i : masik.cnt)
        {
            cnt[i.xx] += i.yy;
        }
        sz += masik.sz;
    }
};

std::vector<int> ans;
data *dfs(int x)
{
    if (adj[x].size() == 0)
    {
        ans[x] = 1;
        return new data();
    }

    std::vector<data *> lst;
    for (auto i : adj[x])
    {
        lst.push_back(dfs(i.first));
    }

    sort(lst.begin(), lst.end(), [&](data *a, data *b) -> bool
         { return a->sz < b->sz; });

    for (int i = 1; i < (int)lst.size(); ++i)
    {
        lst.back()->check(*lst[i - 1]);
    }

    for (int i = 1; i < (int)lst.size(); ++i)
    {
        lst.back()->add(*lst[i - 1]);
        delete lst[i - 1];
    }

    data *curr = new data(x);
    lst.back()->add(*curr, true);

    ans[x] = lst.back()->ok;
    return lst.back();
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    adj.resize(N);
    for (int i = 1; i < N; ++i)
    {
        adj[P[i]].push_back({i, C[i]});
        // adj[i].push_back({P[i], C[i]});
    }

    ans.resize(N);
    dfs(0);
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 228 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 412 KB Output is correct
3 Incorrect 1 ms 304 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 228 KB Output is correct
4 Correct 1 ms 228 KB Output is correct
5 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 228 KB Output is correct
4 Correct 1 ms 228 KB Output is correct
5 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 228 KB Output is correct
4 Correct 1 ms 228 KB Output is correct
5 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -