oj.uz

답안 #841443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
841443 2023-09-01T15:40:18 Z model_code 참나무 (IOI23_beechtree) C++17
13 / 100
 393 ms 86968 KB 
// incorrect/sol_na_wa2.cpp

#include "beechtree.h"
#include <algorithm>
#include <iostream>
#include <map>

#define xx first
#define yy second

#define all(x) (x).begin(), (x).end()

std::vector<std::vector<std::pair<int, int>>> adj;

struct data
{
    bool ok = true;
    int sz = 0;
    std::map<int, int> cnt;

    data() {}

    data(int ind)
    {
        for (auto i : adj[ind])
        {
            sz++;
            cnt[i.yy]++;
            ok &= cnt[i.yy] == 1;
        }
    }

    void add(const data &masik, bool root = false)
    {
        ok &= masik.ok;
        int sum = 0;
        for (auto i : masik.cnt)
        {
            if (!root)
                ok &= i.yy <= cnt[i.xx];
            else
            {
                sum += cnt[i.xx];
            }
            cnt[i.xx] += i.yy;
        }
        if (root)
            ok &= sum == sz;
        sz += masik.sz;
    }
};

std::vector<int> ans;
data *dfs(int x)
{
    if (adj[x].size() == 0)
    {
        ans[x] = 1;
        return new data();
    }

    std::vector<data *> lst;
    for (auto i : adj[x])
    {
        lst.push_back(dfs(i.first));
    }

    sort(lst.begin(), lst.end(), [&](data *a, data *b) -> bool
         { return a->sz < b->sz; });

    for (int i = 1; i < (int)lst.size(); ++i)
    {
        lst.back()->add(*lst[i - 1]);
        delete lst[i - 1];
    }

    data *curr = new data(x);
    lst.back()->add(*curr, true);

    ans[x] = lst.back()->ok;
    return lst.back();
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    adj.resize(N);
    for (int i = 1; i < N; ++i)
    {
        adj[P[i]].push_back({i, C[i]});
        // adj[i].push_back({P[i], C[i]});
    }

    ans.resize(N);
    dfs(0);
    return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 300 KB Output is correct

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 296 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 393 ms 86968 KB Output is correct
8 Correct 209 ms 84644 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 980 KB Output is correct
15 Correct 2 ms 1076 KB Output is correct
16 Correct 2 ms 1112 KB Output is correct
17 Correct 139 ms 79580 KB Output is correct
18 Correct 247 ms 80216 KB Output is correct
19 Correct 193 ms 84700 KB Output is correct
20 Correct 233 ms 86928 KB Output is correct

Subtask #3
0.0 / 9.0

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

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 393 ms 86968 KB Output is correct
6 Correct 209 ms 84644 KB Output is correct
7 Correct 1 ms 224 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 2 ms 608 KB Output is correct
10 Correct 2 ms 480 KB Output is correct
11 Correct 185 ms 35968 KB Output is correct
12 Correct 162 ms 27896 KB Output is correct

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 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 1 ms 308 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 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 1 ms 308 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -