oj.uz

답안 #841415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
841415 2023-09-01T15:39:32 Z model_code 참나무 (IOI23_beechtree) C++17
9 / 100
 93 ms 36308 KB 
// correct/sol_db_shallow.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];
    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;
}

bool distinctCols(int u)
{
    for (auto &pr : graph.col[u])
    {
        auto &[col, vec] = pr;
        if (vec.size() > 1)
        {
            return false;
        }
    }
    return true;
}

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);
        graph.cnt[p]++;
    }
    vector<int> ans(n, 0);
    for (int i = 0; i < n; ++i)
    {
        if (graph.col[i].size() == 0)
        {
            ans[i] = 1;
        }
        else if (i != 0)
        {
            ans[i] = distinctCols(i);
        }
        else
        {
            ans[i] = distinctCols(i);
            vector<pii> children;
            for (auto &pr : graph.col[i])
            {
                for (int v : pr.yy)
                {
                    children.push_back({graph.cnt[v], v});
                }
            }
            sort(all(children));
            for (int j = 0; j < children.size() - 1; ++j)
            {
                ans[i] &= check(children[j].yy, children[j + 1].yy);
            }
            ans[i] &= check(children.back().yy, 0);
        }
    }
    return ans;
}

Compilation message

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

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 5 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9668 KB Output is correct
4 Correct 4 ms 9680 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9640 KB Output is correct
7 Correct 5 ms 9640 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9680 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 78 ms 23092 KB Output is correct
16 Correct 63 ms 22236 KB Output is correct
17 Correct 80 ms 22468 KB Output is correct
18 Correct 68 ms 22792 KB Output is correct

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9668 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Incorrect 93 ms 36308 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 5 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9668 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Correct 4 ms 9696 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9616 KB Output is correct
10 Incorrect 5 ms 9648 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 5 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9668 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Correct 4 ms 9696 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9616 KB Output is correct
10 Incorrect 5 ms 9648 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 5 ms 9684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -