Submission #767070

#	Time	Username	Problem	Language	Result	Execution time	Memory
767070		simene	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	340 KiB

doll

#include "doll.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

class Node 
{
public:
    Node* left;
    Node* right;
    Node* parent;
    bool state = false;
    int ltrig = -1;
    int rtrig = -1;
    int id = -1;

    void construct(int lvls) 
    {
        if (lvls <= 0) return;

        left = new Node();
        right = new Node();

        left->parent = this;
        right->parent = this;

        left->construct(lvls - 1);
        right->construct(lvls - 1);
    }

    Node* traverse() 
    {
        if (left == nullptr) return this;

        if (state) 
        {
            state = !state;
            return right;
        }
        else 
        {
            state = !state;
            return left;
        }
    }

    void insert(int trig) 
    {
        Node* ins = traverse();

        ins->state = !ins->state;

        if (ins->state) ins->ltrig = trig;
        else ins->rtrig = trig;
    }

    int prune() 
    {
        int s = 1;

        if (right != nullptr) s += right->prune();
        if (left != nullptr) s += left->prune();

        if (right == nullptr && rtrig == -1) 
        {
            if (left != nullptr) 
            {
                if (parent->left == this) parent->left = left;
                else parent->right = left;
            }
            else if (ltrig != -1) 
            {
                if (parent->left == this) parent->ltrig = ltrig;
                else parent->rtrig = ltrig;
            }
            else 
            {
                if (parent->left == this) parent->left = nullptr;
                else parent->left = nullptr;

                return 0;
            }
        }

        return s;
    }

    int identify(int nextid, vector<int>* X, vector<int>* Y)
    {
        id = nextid--;

        if (left != nullptr) nextid = left->identify(nextid, X, Y);
        if (right != nullptr) nextid = right->identify(nextid, X, Y);

        if (left != nullptr) (*X)[-id - 1] = left->id;
        else (*X)[-id - 1] = ltrig;

        if (right != nullptr) (*Y)[-id - 1] = right->id;
        else (*Y)[-id - 1] = rtrig;

        return nextid;
    }
};

void create_circuit(int M, std::vector<int> A) 
{
    Node* root;

    A.push_back(0);

    int N = A.size();

    int height = (int)ceil(log2(N));

    root->construct(height);

    for (int i : A) 
    {
        root->insert(i);
    }

    int s = root->prune();

    vector<int> C(M + 1);
    for (int i = 0; i < M + 1; i++) C[i] = -1;

    vector<int> X(s);
    vector<int> Y(s);

    root->identify(-1, &X, &Y);

    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:116:20: warning: 'root' is used uninitialized in this function [-Wuninitialized]
  116 |     root->construct(height);
      |     ~~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56