Submission #75293

#	Time	Username	Problem	Language	Result	Execution time	Memory
75293		Coisin	Mechanical Doll (IOI18_doll)	C++14	53 / 100	797 ms	47420 KiB

doll

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

using namespace std;

int num_triggers;
int num_nodes;
vector<int> visit_order;

vector<vector<int> > adjList, triggerEdgeList;
vector<bool> mode; // 1 = X, 0 = Y
vector<int> triggerVisitCounter;
vector<int> parentTrigger;
vector<int> parentRoot;

int required_number_of_leaves(int num_out_edges) {
  if(num_out_edges == 0)
    return 0;
  int depth = log2(num_out_edges);
  if(1 << depth != num_out_edges)
    depth++;
  return 1 << depth;
}

void switch_mode(int node) {
  mode[node] = !mode[node];
}

int create_switch(int num_children, int parent, bool root, int root_node) {
  int node_number = num_nodes++;
  if(root)
    root_node = node_number;
  parentTrigger.push_back(parent);
  parentRoot.push_back(root_node);
  triggerVisitCounter.push_back(0);
  adjList.push_back(vector<int>() );
  mode.push_back(1);
  if(num_children == 2) {
    adjList[node_number].push_back(-1);
    adjList[node_number].push_back(-1);
  } else {
    int left_node = create_switch(num_children / 2, parent, false, root_node);
    int right_node = create_switch(num_children / 2, parent, false, root_node);
    adjList[node_number].push_back(left_node);
    adjList[node_number].push_back(right_node);
  }
  return node_number;
}

int tree_interator;

int find_next_tree() {
  while(tree_interator < num_nodes) {
    if(parentRoot[tree_interator] == tree_interator && triggerVisitCounter[tree_interator] < required_number_of_leaves(triggerEdgeList[parentTrigger[tree_interator]].size()))
      return tree_interator;
    tree_interator++;
  }
  return 0;
}
bool origin_visited = false;

int occur = 0;
  
void build_graph(int current_node) {
  if(current_node == 0) {

    //cout << "VISITED" << endl;
    if(origin_visited)
      return;
    origin_visited = true;
  }
  if(current_node >= num_triggers) { // Switch
    if(parentRoot[current_node] == current_node) {
      triggerVisitCounter[current_node]++;
    }

    int leaves_in_binary_tree = required_number_of_leaves(triggerEdgeList[parentTrigger[current_node]].size());
    //cout << leaves_in_binary_tree << endl;
    int num_visits = triggerVisitCounter[parentRoot[current_node]];
    int num_outgoing_triggers = triggerEdgeList[parentTrigger[current_node]].size();

    int next_node;
    //cout << current_node << ", " << mode[current_node] << endl;
    if(mode[current_node]) { // X
      if(adjList[current_node][0] == -1) {
        if(num_visits <= num_outgoing_triggers) {
          adjList[current_node][0] = triggerEdgeList[parentTrigger[current_node]][triggerVisitCounter[parentRoot[current_node]] - 1];
        } else if(num_visits < leaves_in_binary_tree) {
          adjList[current_node][0] = parentRoot[current_node];
        } else if(num_visits == leaves_in_binary_tree) {
          adjList[current_node][0] = find_next_tree();
        }
      }
      if(adjList[current_node][0] == -1) {
        adjList[current_node][0] = find_next_tree();
      }
      next_node = adjList[current_node][0];
    } else { // Y
      if(adjList[current_node][1] == -1) {
        if(num_visits <= num_outgoing_triggers) {
          adjList[current_node][1] = triggerEdgeList[parentTrigger[current_node]][triggerVisitCounter[parentRoot[current_node]] - 1];
        } else if(num_visits < leaves_in_binary_tree) {
          adjList[current_node][1] = parentRoot[current_node];
        } else if(num_visits == leaves_in_binary_tree) {
          adjList[current_node][1] = find_next_tree();
        }
      }
      if(adjList[current_node][1] == -1) {
        adjList[current_node][1] = find_next_tree();
      }
      next_node = adjList[current_node][1];
    }
    switch_mode(current_node);
    build_graph(next_node);
  } else { // Trigger
    //cout << current_node << endl;
    //cout << current_node << endl;
    if(current_node && visit_order[occur++] != current_node) {
      cerr << occur << endl;
    }
    if(adjList[current_node].empty()) { // Not Built Yet
      if(triggerEdgeList[current_node].size() == 0) {
        adjList[current_node].push_back(find_next_tree());
      } else if(triggerEdgeList[current_node].size() == 1) { // Directly
        adjList[current_node].push_back(triggerEdgeList[current_node][0]);
      } else { // Requires Switch
        int num_leaves = required_number_of_leaves(triggerEdgeList[current_node].size());
        int switch_node = create_switch(num_leaves, current_node, true, -1);
        adjList[current_node].push_back(switch_node);
      }
    }

    if(adjList[current_node][0] == -1)
      adjList[current_node][0] = find_next_tree();
    build_graph(adjList[current_node][0]);
  }
}

int format_serial(int x) {
  if(x >= num_triggers) {
    return -((x - num_triggers) + 1);
  }
  return x;
}

void create_circuit(int _num_triggers, vector<int> _visit_order) {
  num_triggers = num_nodes = _num_triggers + 1;
  visit_order = _visit_order;

  adjList.assign(num_triggers, vector<int>() );
  triggerEdgeList.assign(num_triggers, vector<int>() );
  triggerVisitCounter.assign(num_triggers, 0);
  parentTrigger.assign(num_triggers, -1);
  parentRoot.assign(num_triggers, -1);
  mode.assign(num_triggers, 0);

  int current_node = 0;
  for(int next_node : visit_order) {
    triggerEdgeList[current_node].push_back(next_node);
    current_node = next_node;
  }
  triggerEdgeList[current_node].push_back(-1);
  tree_interator = num_triggers;
  build_graph(0);
  vector<int> C(num_triggers), X, Y;
  for(int i = 0; i < num_triggers; i++) {
    if(adjList[i].size() == 0)
      adjList[i].push_back(0);
    C[i] = format_serial(adjList[i][0]);
  }
  for(int i = 0; i + num_triggers < num_nodes; i++) {
    int node_number = num_triggers + i;
    X.push_back(format_serial(adjList[node_number][0]));
    Y.push_back(format_serial(adjList[node_number][1]));
  }
  for(int i = 0; i < num_triggers; i++) {
    //cout << i << ", " << C[i] << endl;
  }
  for(int i = 0; i + num_triggers < num_nodes; i++) {
    //cout << format_serial(i + num_triggers) << ", " << mode[i + num_triggers] << " - " << X[i] << ", " << Y[i] << endl;
  }
  answer(C, X, Y);
}

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