Submission #1039046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039046		fv3	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2083 ms	26864 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);
        }
    }

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

        bool ok = true;
        for (auto child : children)
        {
            if (cnt[c[child]]++ != label[p[child]])
            {
                ok = false;
                break;
            }
        }

        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:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i < children.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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