oj.uz

Submission #75293

# Submission time Handle Problem Language Result Execution time Memory
75293 2018-09-09T06:50:03 Z Coisin Mechanical Doll (IOI18_doll) C++14
53 / 100
 797 ms 47420 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 13256 KB Output is correct
3 Correct 37 ms 9804 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 25 ms 10444 KB Output is correct
6 Correct 75 ms 14772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 13256 KB Output is correct
3 Correct 37 ms 9804 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 25 ms 10444 KB Output is correct
6 Correct 75 ms 14772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 140 ms 17180 KB Output is correct
9 Correct 138 ms 19172 KB Output is correct
10 Correct 207 ms 26484 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 13256 KB Output is correct
3 Correct 37 ms 9804 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 25 ms 10444 KB Output is correct
6 Correct 75 ms 14772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 140 ms 17180 KB Output is correct
9 Correct 138 ms 19172 KB Output is correct
10 Correct 207 ms 26484 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 275 ms 31912 KB Output is correct
15 Correct 126 ms 16184 KB Output is correct
16 Correct 236 ms 24428 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 310 ms 28700 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 216 ms 16112 KB Output is correct
3 Partially correct 694 ms 30612 KB Output is partially correct
4 Partially correct 669 ms 31408 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 216 ms 16112 KB Output is correct
3 Partially correct 694 ms 30612 KB Output is partially correct
4 Partially correct 669 ms 31408 KB Output is partially correct
5 Partially correct 346 ms 38468 KB Output is partially correct
6 Partially correct 423 ms 41700 KB Output is partially correct
7 Partially correct 373 ms 40948 KB Output is partially correct
8 Partially correct 437 ms 44724 KB Output is partially correct
9 Partially correct 509 ms 29332 KB Output is partially correct
10 Partially correct 797 ms 45132 KB Output is partially correct
11 Partially correct 625 ms 47420 KB Output is partially correct
12 Partially correct 358 ms 29784 KB Output is partially correct
13 Partially correct 286 ms 27128 KB Output is partially correct
14 Partially correct 239 ms 26608 KB Output is partially correct
15 Partially correct 191 ms 25908 KB Output is partially correct
16 Partially correct 8 ms 920 KB Output is partially correct
17 Partially correct 270 ms 23620 KB Output is partially correct
18 Partially correct 271 ms 23648 KB Output is partially correct
19 Partially correct 340 ms 25068 KB Output is partially correct
20 Partially correct 438 ms 32972 KB Output is partially correct
21 Partially correct 500 ms 39088 KB Output is partially correct
22 Partially correct 357 ms 29420 KB Output is partially correct