oj.uz

Submission #841433

# Submission time Handle Problem Language Result Execution time Memory
841433 2023-09-01T15:40:04 Z model_code Beech Tree (IOI23_beechtree) C++17
22 / 100
 205 ms 69264 KB 
// incorrect/sol_na_wa6.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)
            {
                // std::cerr<<i.xx<<" "<<i.yy<<" "<<cnt[i.xx]<<"\n";
                ok &= i.yy <= cnt[i.xx];
                if (cnt[i.xx] >= 1)
                    ok &= i.yy > 0;
            }

            sum += cnt[i.xx];
        }

        if (root)
            ok &= sum == sz;
        else
        {
            ok &= sz - sum == (int)cnt.size() - (int)masik.cnt.size();
        }
    }

    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[i]->check(*lst[i - 1]);
    }
    data *curr = new data(x);
    lst.back()->check(*curr, true);

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

    lst.back()->add(*curr, true);
    delete curr;

    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 228 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 228 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 228 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 228 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 0 ms 228 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 0 ms 224 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 228 KB Output is correct
18 Correct 0 ms 228 KB Output is correct
19 Correct 0 ms 228 KB Output is correct
20 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
21 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 228 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 192 ms 69264 KB Output is correct
8 Correct 146 ms 66916 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 1 ms 356 KB Output is correct
12 Correct 0 ms 356 KB Output is correct
13 Correct 2 ms 864 KB Output is correct
14 Correct 1 ms 864 KB Output is correct
15 Correct 2 ms 984 KB Output is correct
16 Correct 2 ms 992 KB Output is correct
17 Correct 96 ms 62008 KB Output is correct
18 Correct 92 ms 62224 KB Output is correct
19 Correct 171 ms 66472 KB Output is correct
20 Correct 180 ms 68144 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Correct 1 ms 228 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 228 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 228 KB Output is correct
8 Correct 0 ms 228 KB Output is correct
9 Correct 1 ms 228 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 304 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 86 ms 11800 KB Output is correct
16 Correct 80 ms 11164 KB Output is correct
17 Correct 81 ms 11356 KB Output is correct
18 Correct 98 ms 11700 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 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 316 KB Output is correct
5 Correct 192 ms 69264 KB Output is correct
6 Correct 146 ms 66916 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 205 ms 25216 KB Output is correct
12 Correct 185 ms 19576 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 228 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 228 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 228 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 228 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 0 ms 224 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 228 KB Output is correct
21 Correct 0 ms 228 KB Output is correct
22 Correct 0 ms 228 KB Output is correct
23 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 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 316 KB Output is correct
5 Correct 0 ms 228 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 228 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 0 ms 224 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 228 KB Output is correct
14 Correct 0 ms 228 KB Output is correct
15 Correct 0 ms 228 KB Output is correct
16 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 228 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 228 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 228 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 228 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 0 ms 224 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 228 KB Output is correct
21 Correct 0 ms 228 KB Output is correct
22 Correct 0 ms 228 KB Output is correct
23 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 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 316 KB Output is correct
5 Correct 0 ms 228 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 228 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 0 ms 224 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 228 KB Output is correct
14 Correct 0 ms 228 KB Output is correct
15 Correct 0 ms 228 KB Output is correct
16 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 228 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 228 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 228 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 228 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 0 ms 224 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 228 KB Output is correct
21 Correct 0 ms 228 KB Output is correct
22 Correct 0 ms 228 KB Output is correct
23 Incorrect 0 ms 228 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -