답안 #846826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846826	2023-09-08T13:47:58 Z	ogkostya	참나무 (IOI23_beechtree)	C++17	5 / 100	46 ms	9680 KB

beechtree

#include "beechtree.h"
#include <algorithm> 
#include <queue>
#include <set>
int cn[200010];
int lev[200010];
std::vector<int> down[200010];

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    std::vector<int> ans{  };

    bool sub2 = true;
    for (int i = 1; sub2 && i < N; i++)
    {
        sub2 &= P[i] == i - 1;
    }

    if (sub2)
    {
        ans.push_back(1);
        ans.push_back(1);
        for (int i = N - 3; i >= 0; i--)
        {
            sub2 &= C[i + 1] == C[N - 1];
            ans.push_back(sub2 ? 1 : 0);
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }

    // sub 4
    std::fill_n(cn, M+1, 0);
    bool sub4 = true;
    for (size_t i = 0; i < C.size(); i++)
    {
        if (++cn[C[i]] > 2)
        {
            sub4 = false;
            break;
        }
    }
    if (sub4)
    {
        for (int i = 1; i < N; i++)
        {
            down[P[i]].push_back(i);
        }
        std::queue<int> q = {};
        std::fill_n(lev, N + 1, 0);
        std::fill_n(cn, N + 1, 0);
        for (int i = 0; i < N; i++)
        {
            cn[i] = down[i].size();
            if (down[i].size() == 0)
            {
                q.push(i);
            }
        }
        while (q.size() > 0)
        {
            int ii = q.front();
            q.pop();

            if (ii == 0)
                break;
            
            if (--cn[P[ii]] == 0)
            {
                q.push(P[ii]);
                lev[P[ii]] = 1 + lev[ii];
            }
        }

        for (int i = 0; i < N; i++)
        {
            if (lev[i] == 0)
            {
                ans.push_back(1);
            }
            else if (lev[i] == 1)
            {
                std::set<int> s = {};
                bool ok = true;
                for (size_t j = 0; j < down[i].size(); j++)
                {
                    if (s.count(C[down[i][j]]) == 0)
                    {
                        s.insert(C[down[i][j]]);
                    }
                    else
                    {
                        ok = false;
                        break;
                    }
                }
                ans.push_back(ok ? 1 : 0);
            }
            else if (lev[i] == 2)
            {
                std::set<int> s = {};
                bool ok = true;
                int f = -1;
                for (size_t j = 0; j < down[i].size(); j++)
                {
                    if (down[down[i][j]].size() > 0)
                    {
                        if (f == -1)
                        {
                            f = down[i][j];
                        }
                        else
                        {
                            ok = false;
                            break;
                        }
                    }
                    if (s.count(C[down[i][j]]) == 0)
                    {
                        s.insert(C[down[i][j]]);
                    }
                    else
                    {
                        ok = false;
                        break;
                    }
                }
                if (ok)
                {
                    for (size_t j = 0; j < down[f].size(); j++)
                    {
                        if (s.count(C[down[i][j]]) == 1)
                        {
                            s.erase(C[down[i][j]]);
                        }
                        else
                        {
                            ok = false;
                            break;
                        }
                    }
                }
                ans.push_back(ok ? 1 : 0);
            }
            else
            {
                ans.push_back(0);
            }
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 18 tokens, found 0 tokens
3	Halted	0 ms	0 KB	-

Subtask #1
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5464 KB	Output is correct
4	Correct	2 ms	5464 KB	Output is correct
5	Correct	2 ms	5464 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5464 KB	Output is correct
8	Correct	1 ms	5464 KB	Output is correct
9	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 7 tokens, found 0 tokens
10	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5464 KB	Output is correct
4	Correct	2 ms	5464 KB	Output is correct
5	Correct	2 ms	5464 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	46 ms	9672 KB	Output is correct
8	Correct	45 ms	9672 KB	Output is correct
9	Correct	2 ms	5720 KB	Output is correct
10	Correct	1 ms	5464 KB	Output is correct
11	Correct	1 ms	5464 KB	Output is correct
12	Correct	1 ms	5464 KB	Output is correct
13	Correct	2 ms	5464 KB	Output is correct
14	Correct	2 ms	5464 KB	Output is correct
15	Correct	2 ms	5464 KB	Output is correct
16	Correct	2 ms	5464 KB	Output is correct
17	Correct	45 ms	9680 KB	Output is correct
18	Correct	44 ms	9672 KB	Output is correct
19	Correct	44 ms	9672 KB	Output is correct
20	Correct	45 ms	9676 KB	Output is correct

Subtask #3
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 115 tokens, found 0 tokens
2	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5464 KB	Output is correct
4	Correct	1 ms	5464 KB	Output is correct
5	Correct	46 ms	9672 KB	Output is correct
6	Correct	45 ms	9672 KB	Output is correct
7	Incorrect	2 ms	5464 KB	2nd lines differ - on the 32nd token, expected: '0', found: '1'
8	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 18 tokens, found 0 tokens
3	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5464 KB	Output is correct
4	Correct	1 ms	5464 KB	Output is correct
5	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 7 tokens, found 0 tokens
6	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 18 tokens, found 0 tokens
3	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5464 KB	Output is correct
4	Correct	1 ms	5464 KB	Output is correct
5	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 7 tokens, found 0 tokens
6	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Incorrect	1 ms	5464 KB	2nd lines differ - expected: 18 tokens, found 0 tokens
3	Halted	0 ms	0 KB	-

답안 #846826

Compilation message