oj.uz

Submission #767070

# Submission time Handle Problem Language Result Execution time Memory
767070 2023-06-26T11:03:49 Z simene Mechanical Doll (IOI18_doll) C++14
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -