Submission #1039052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039052		fv3	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2096 ms	36048 KiB

beechtree

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

using namespace std;
vector<int> b, p, c;
vector<vector<int>> adj;

void solve(int index)
{
    vector<int> children;
    queue<int> q;
    q.push(index);

    while (!q.empty())
    {
        int s = q.front();
        q.pop();
        for (auto node : adj[s])
        {
            children.push_back(node);
            q.push(node);
        }
    }

    b[index] = 1;
    if (!children.size())
        return;

    sort(children.begin(), children.end());
    do
    {
        map<int, int> cnt;
        map<int, int> label;
        label[index] = 0;
        for (int i = 0; i < children.size(); i++)
            label[children[i]] = i+1;

        if (index == 0)
        {
            for (auto e : label)
                cerr << e.second << ' ';
            cerr << "= ";
        }

        bool ok = true;
        for (auto child : children)
        {
            if (cnt[c[child]] != label[p[child]])
            {
                cerr << child << ", " << label[p[child]] << ", " << cnt[c[child]] << '\n';
                ok = false;
                break;
            }
            cnt[c[child]]++;
        }
        if (ok)
        {
            return;
        }
    } while (next_permutation(children.begin(), children.end()));

    b[index] = 0;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
    p = P; c = C;
    b = vector<int>(N);
    adj = vector<vector<int>>(N);

    for (int i = 1; i < N; i++)
        adj[P[i]].push_back(i);

    for (int i = 0; i < N; i++)
    {
        solve(i);
    }

    return b;
}

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12