oj.uz

Submission #1030050

# Submission time Handle Problem Language Result Execution time Memory
1030050 2024-07-21T17:39:04 Z Mr_Husanboy Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 41744 KB 
// #include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

const int c = 200005;
int n, szint[c], cl[c];
vector<int> sz[c], szin[c], ans;
bool ism[c];
void dfs(int a)
{
    for (auto x : sz[a])
    {
        szint[x] = szint[a] + 1;
        dfs(x);
        if (ism[x])
        {
            ism[a] = 1;
        }
    }
}
bool is_subset(int a, int b)
{
    // a-ban van tobb
    int pos = 0, si = szin[b].size();
    for (auto x : szin[a])
    {
        if (pos < si && x == szin[b][pos])
        {
            pos++;
        }
    }
    return (pos == si);
}
vector<pair<int, int>> sor;
void dfs2(int a)
{
    int si = sz[a].size();
    sor.push_back({-si, a});
    for (auto x : sz[a])
    {
        dfs2(x);
    }
}
bool solve(int a)
{
    // cout << "solve " << a << "\n";
    dfs2(a);
    sort(sor.begin(), sor.end());
    int si = sor.size();
    bool jo = 1;
    for (int i = 1; i < si; i++)
    {
        if (!is_subset(sor[i - 1].second, sor[i].second))
        {
            jo = 0;
        }
    }
    for (int i = 0; i < si; i++)
    {
        for (int j = i + 1; j < si; j++)
        {
            int a = sor[i].second, b = sor[j].second;
            if (cl[a] == cl[b] && a > b)
            {
                jo = 0;
            }
        }
    }
    sor.clear();
    return jo;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N;
    for (int i = 1; i < n; i++)
    {
        sz[P[i]].push_back(i);
        szin[P[i]].push_back(C[i]);
        cl[i] = C[i];
    }
    for (int i = 0; i < n; i++)
    {
        sort(szin[i].begin(), szin[i].end());
        for (int j = 1; j < szin[i].size(); j++)
        {
            if (szin[i][j] == szin[i][j - 1])
            {
                ism[i] = 1;
            }
        }
    }
    dfs(0);

    for (int i = 0; i < n; i++)
    {
        if (ism[i])
        {
            ans.push_back(0);
        }
        else
        {
            ans.push_back(solve(i));
        }
    }
    return ans;
}

/*
int main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    std::vector<int> P(N);
    for(int i = 0; i < N; ++i)
        assert (1 == scanf("%d", &P[i]));
    std::vector<int> C(N);
    for(int i = 0; i < N; ++i)
        assert (1 == scanf("%d", &C[i]));

    fclose(stdin);

    std::vector<int> res = beechtree(N, M, P, C);

    int n = res.size();
    for (int i = 0; i < n; ++i) {
        if (i > 0)
            printf(" ");
        printf("%d", res[i]);
    }
    printf("\n");
    fclose(stdout);

    return 0;
}
*/
/*
3 3
-1 0 0
0 1 2
*/
/*
18 3
-1 0 0 0 1 1 1 2 2 3 3 3 4 4 5 10 11 11
0 1 2 3 1 2 3 1 3 3 2 1 1 2 2 1 2 3

*/

Compilation message

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10684 KB Output is correct
6 Correct 3 ms 10740 KB Output is correct
7 Execution timed out 2024 ms 41744 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

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

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Execution timed out 2024 ms 41744 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10684 KB Output is correct
9 Correct 3 ms 10740 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Incorrect 3 ms 10584 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10684 KB Output is correct
9 Correct 3 ms 10740 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Incorrect 3 ms 10584 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10684 KB Output is correct
9 Correct 3 ms 10740 KB Output is correct
10 Correct 3 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Incorrect 3 ms 10584 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -