oj.uz

Submission #841430

# Submission time Handle Problem Language Result Execution time Memory
841430 2023-09-01T15:39:57 Z model_code Beech Tree (IOI23_beechtree) C++17
22 / 100
 181 ms 67588 KB 
// incorrect/sol_db_fake.cpp

#include "beechtree.h"
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 1;

struct Graph
{
    int cnt[N];
    bool con[N];
    map<int, vector<int>> col[N];
} graph;

bool check(int v, int u)
{
    for (auto &pr : graph.col[v])
    {
        auto &[col, vec] = pr;
        auto it = graph.col[u].find(col);
        if (it == graph.col[u].end() || graph.cnt[vec[0]] > graph.cnt[it->yy[0]])
        {
            return false;
        }
    }
    return true;
}

int dfs(int u)
{
    graph.cnt[u] = 1;
    graph.con[u] = true;

    vector<pii> srt;
    for (auto &pr : graph.col[u])
    {
        auto &[col, vec] = pr;
        graph.con[u] &= vec.size() == 1;

        for (int v : vec)
        {
            int cnv = dfs(v);
            if (cnv == -1)
            {
                graph.con[u] = false;
            }
            else
            {
                graph.cnt[u] += cnv;
            }
            srt.push_back({cnv, v});
        }
    }
    srt.push_back({graph.cnt[u], u});
    sort(all(srt));

    for (int i = 0; i < srt.size() - 1; ++i)
    {
        graph.con[u] = graph.con[u] & check(srt[i].yy, srt[i + 1].yy);
    }
    return graph.con[u] ? graph.cnt[u] : -1;
}

vector<int> beechtree(int n, int m, vector<int> P, vector<int> C)
{
    for (int i = 1; i < n; ++i)
    {
        int p = P[i];
        int c = C[i];
        if (!graph.col[p].count(c))
        {
            graph.col[p][c] = vector<int>();
        }
        graph.col[p][c].push_back(i);
    }
    dfs(0);

    vector<int> ans;
    for (int i = 0; i < n; ++i)
        ans.push_back(graph.con[i]);
    return ans;
}

Compilation message

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9692 KB Output is correct
3 Correct 4 ms 9692 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9696 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9704 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9700 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9580 KB Output is correct
12 Correct 6 ms 9632 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9696 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9704 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 114 ms 67500 KB Output is correct
8 Correct 115 ms 67588 KB Output is correct
9 Correct 7 ms 9696 KB Output is correct
10 Correct 5 ms 9696 KB Output is correct
11 Correct 6 ms 9696 KB Output is correct
12 Correct 6 ms 9712 KB Output is correct
13 Correct 7 ms 10240 KB Output is correct
14 Correct 9 ms 10228 KB Output is correct
15 Correct 7 ms 10208 KB Output is correct
16 Correct 5 ms 10208 KB Output is correct
17 Correct 107 ms 64980 KB Output is correct
18 Correct 117 ms 65016 KB Output is correct
19 Correct 110 ms 64948 KB Output is correct
20 Correct 108 ms 65052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9696 KB Output is correct
2 Correct 6 ms 9616 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 5 ms 9652 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 6 ms 9700 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 8 ms 9816 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9852 KB Output is correct
14 Correct 6 ms 9836 KB Output is correct
15 Correct 93 ms 24828 KB Output is correct
16 Correct 84 ms 24020 KB Output is correct
17 Correct 90 ms 24084 KB Output is correct
18 Correct 87 ms 24552 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 114 ms 67500 KB Output is correct
6 Correct 115 ms 67588 KB Output is correct
7 Correct 6 ms 9704 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 19 ms 9944 KB Output is correct
11 Correct 126 ms 39836 KB Output is correct
12 Correct 181 ms 37120 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9692 KB Output is correct
3 Correct 4 ms 9692 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9704 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9700 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9580 KB Output is correct
15 Correct 6 ms 9632 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9580 KB Output is correct
8 Correct 6 ms 9632 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9692 KB Output is correct
3 Correct 4 ms 9692 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9704 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9700 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9580 KB Output is correct
15 Correct 6 ms 9632 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9580 KB Output is correct
8 Correct 6 ms 9632 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9692 KB Output is correct
3 Correct 4 ms 9692 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9704 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9700 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9580 KB Output is correct
15 Correct 6 ms 9632 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Incorrect 6 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -