Submission #912599

#	Time	Username	Problem	Language	Result	Execution time	Memory
912599		Ludissey	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2090 ms	20384 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>> child;
vector<int> C;
vector<int> P;
vector<int> outp;


std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
    N=n; M=m;
    C.assign(c.begin(), c.end());
    P.assign(p.begin(), p.end());
    child.resize(n);
    outp.resize(n,0);
    for (int i = 1; i < N; i++) child[P[i]].push_back(i);
    
    for (int i = 0; i < N; i++)
    {
        vector<int> perm;
        queue<int> queue;
        queue.push(i);
        while(!queue.empty()){
            int x=queue.front(); queue.pop();
            perm.push_back(x);
            for (auto u : child[x]) queue.push(u);
        }
        sort(perm.begin()+1, perm.end());
        if(perm.size()==1) outp[i]=1;
        do {
            map<int, int> ccnt; 
            bool b=true;
            for (int j = 1; j < perm.size(); j++)
            {
                if(ccnt.find(c[perm[j]])==ccnt.end()) ccnt[c[perm[j]]]=0;
                if(perm[ccnt[c[perm[j]]]]!=P[perm[j]]) {
                    b=false;
                    break;
                }
                ccnt[c[perm[j]]]++;
            }
            if(b) { outp[i]=1; break; }
        } while(next_permutation(perm.begin()+1, perm.end()));
    }
    

    return {outp};
}

Compilation message (stderr)

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

• 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