oj.uz

Submission #841434

# Submission time Handle Problem Language Result Execution time Memory
841434 2023-09-01T15:40:05 Z model_code Beech Tree (IOI23_beechtree) C++17
22 / 100
 242 ms 52916 KB 
// incorrect/sol_na_full-2-wa.cpp

#include "beechtree.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <functional>
#include <queue>

#define xx first
#define yy second

std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> sz;
std::vector<int> par;
std::vector<int> par_c;
std::vector<int> ans;

void dfs(int x)
{
    sz[x] = 1;
    for (auto i : adj[x])
    {
        dfs(i.xx);
        par[i.xx] = x;
        par_c[i.xx] = i.yy;
        sz[x] += sz[i.xx];
    }
}

std::vector<int> ccnt, ocnt, where;
bool check(int x)
{
    bool ok = true;
    std::vector<int> ord = {};
    std::vector<std::pair<int, int>> edgs, edgs2;
    std::function<void(int, bool)> dfs2;

    dfs2 = [&](int x, bool root)
    {
        if (root)
        {
            where[x] = ord.size();
            ord.push_back(x);
        }
        for (auto i : adj[x])
        {
            ccnt[i.yy]++;
            ok &= ccnt[i.yy] <= 1;
            where[i.xx] = ord.size();
            edgs.push_back({ocnt[i.yy]++, ord.size()});
            ord.push_back(i.xx);
        }
        for (auto i : adj[x])
        {
            ccnt[i.yy]--;
        }
        for (auto i : adj[x])
        {
            dfs2(i.xx, false);
        }
    };

    dfs2(x, true);
    for (int i = 1; i < ord.size(); ++i)
    {
        ocnt[par_c[ord[i]]] = 0;
    }
    for (int i = 1; i < (int)ord.size(); ++i)
    {
        edgs2.push_back({where[par[ord[i]]], i});
    }

    ok &= edgs == edgs2;

    return ok;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    adj.resize(N);
    sz.resize(N);
    par.assign(N, -1);
    par_c.assign(N, 0);
    ans.assign(N, -1);
    ccnt.assign(M + 1, 0);
    ocnt.assign(M + 1, 0);
    where.assign(N, -1);
    for (int i = 1; i < N; ++i)
    {
        adj[P[i]].push_back({i, C[i]});
    }

    dfs(0);
    for (int i = 0; i < N; ++i)
    {
        sort(adj[i].begin(), adj[i].end(), [&](auto &x, auto &y) -> bool
             { return sz[x.xx] > sz[y.xx]; });
    }

    std::priority_queue<std::pair<int, int>> c;
    std::vector<int> rnd_val(N);
    for (int i = 0; i < N; ++i)
    {
        rnd_val[i] = rand();
        c.push({rnd_val[i], i});
    }

    std::function<void(int)> filldfs;
    filldfs = [&](int x)
    {
        if (rnd_val[x] == -1)
            return;
        ans[x] = 1;
        rnd_val[x] = -1;
        for (auto i : adj[x])
        {
            filldfs(i.xx);
        }
    };

    auto changepars = [&](int x)
    {
        while (x != -1)
        {
            if (rnd_val[x] == -1)
                return;
            ans[x] = 0;
            rnd_val[x] = -1;
            x = par[x];
        }
    };

    while (!c.empty())
    {
        auto x = c.top();
        c.pop();
        if (x.xx != rnd_val[x.yy])
            continue;
        if (check(x.yy))
        {
            filldfs(x.yy);
        }
        else
        {
            changepars(x.yy);
        }
    }
    return ans;
}

Compilation message

beechtree.cpp: In function 'bool check(int)':
beechtree.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 1; i < ord.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 220 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 220 KB Output is correct
9 Correct 1 ms 224 KB Output is correct
10 Correct 0 ms 224 KB Output is correct
11 Correct 0 ms 216 KB Output is correct
12 Correct 1 ms 220 KB Output is correct
13 Correct 1 ms 224 KB Output is correct
14 Correct 1 ms 224 KB Output is correct
15 Correct 1 ms 224 KB Output is correct
16 Correct 0 ms 224 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 224 KB Output is correct
19 Correct 1 ms 216 KB Output is correct
20 Incorrect 0 ms 212 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 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 220 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 119 ms 41100 KB Output is correct
8 Correct 106 ms 41148 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 2 ms 2260 KB Output is correct
16 Correct 2 ms 2356 KB Output is correct
17 Correct 155 ms 52688 KB Output is correct
18 Correct 242 ms 52880 KB Output is correct
19 Correct 146 ms 52916 KB Output is correct
20 Correct 97 ms 41140 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 1972 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 3 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 76 ms 14212 KB Output is correct
16 Correct 77 ms 13580 KB Output is correct
17 Correct 81 ms 13720 KB Output is correct
18 Correct 49 ms 14024 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 119 ms 41100 KB Output is correct
6 Correct 106 ms 41148 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 2004 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct
11 Correct 143 ms 23256 KB Output is correct
12 Correct 109 ms 22064 KB Output is correct

Subtask #5
0.0 / 14.0

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