oj.uz

Submission #1073714

# Submission time Handle Problem Language Result Execution time Memory
1073714 2024-08-24T18:57:00 Z vjudge1 Simurgh (IOI17_simurgh) C++17
0 / 100
 123 ms 50100 KB 
#include "simurgh.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
// #include <iostream>
#include <iterator>
#include <optional>
#include <vector>
using namespace std;

enum class SeenState { seen, in_progress, not_seen };

struct Adjacency {
  int id;
  int to;
};

struct TreeNode {
  vector<Adjacency> children;
  vector<Adjacency> backedges;
  optional<Adjacency> parent;

  SeenState seen = SeenState::not_seen;
};

void dfs(vector<TreeNode> &tree,
         const vector<vector<Adjacency>> &adjacency_list, int current = 0) {
  tree.at(current).seen = SeenState::in_progress;
  // cout << "seen " << current << '\n';
  const vector<Adjacency> &neighbors = adjacency_list.at(current);

  for (Adjacency adjacency : neighbors) {
    int neighbor = adjacency.to;

    if (tree.at(neighbor).seen != SeenState::not_seen) {
      if (tree.at(neighbor).seen == SeenState::in_progress) {
        if (!tree.at(current).parent.has_value() ||
            (tree.at(current).parent.value().to != neighbor)) {
          tree.at(current).backedges.push_back(adjacency);
        }
      }
      continue;
    }

    tree.at(current).children.push_back(adjacency);
    tree.at(neighbor).parent = {adjacency.id, current};

    dfs(tree, adjacency_list, adjacency.to);
  }

  tree.at(current).seen = SeenState::seen;
}

vector<TreeNode> build_tree(int city_count, const vector<int> &a,
                            const vector<int> &b) {
  vector<TreeNode> tree(city_count);
  vector<vector<Adjacency>> adjacency_list(city_count);

  for (int i = 0;
       i < static_cast<int>(a.size()) && i < static_cast<int>(b.size()); ++i) {
    adjacency_list.at(a.at(i)).push_back({i, static_cast<int>(b.at(i))});
    adjacency_list.at(b.at(i)).push_back({i, static_cast<int>(a.at(i))});
  }

  dfs(tree, adjacency_list);

  return tree;
}

struct Backedge {
  int id;
  vector<int> spanning_edges;
};

vector<Backedge> get_backedges(const vector<TreeNode> &tree) {
  vector<Backedge> backedges;

  for (int i = 0; i < static_cast<int>(tree.size()); ++i) {
    const TreeNode &node = tree.at(i);

    for (Adjacency adjacency : node.backedges) {
      Backedge backedge{adjacency.id, {}};

      // cout << "backedge " << adjacency.id << " of " << i << " goes to "
      //      << adjacency.to << '\n';

      int current = i;
      while (current != adjacency.to) {
        // cout << "finding parent of " << current << '\n';
        backedge.spanning_edges.push_back(tree.at(current).parent.value().id);
        current = tree.at(current).parent.value().to;
      }

      backedges.push_back(backedge);
    }
  }

  return backedges;
}

vector<int> get_initial(const vector<TreeNode> &tree) {
  vector<int> initial;

  for (const TreeNode &tree_node : tree) {
    for (Adjacency child : tree_node.children) {
      initial.push_back(child.id);
    }
  }

  return initial;
}

enum class Edge {
  Present,
  Unknown,
  Absent,
};

inline void test_by_cycle(int spanning_edge, vector<int> &current_golden,
                          vector<Edge> &edges, int backedge, int init_res) {
  size_t spanning_edge_i = distance(
      current_golden.begin(),
      lower_bound(current_golden.begin(), current_golden.end(), spanning_edge));

  assert(current_golden.at(spanning_edge_i) == spanning_edge);

  current_golden.at(spanning_edge_i) = backedge;
  int new_res = count_common_roads(current_golden);

  if (new_res > init_res) {
    // cout << backedge << " is present. " << spanning_edge << " is absent.\n";
    edges.at(backedge) = Edge::Present;
    edges.at(spanning_edge) = Edge::Absent;
  }

  if (new_res < init_res) {
    // cout << spanning_edge << " is present. " << backedge << " is absent.\n";
    edges.at(spanning_edge) = Edge::Present;
    edges.at(backedge) = Edge::Absent;
  }

  if (new_res == init_res) {
    if (edges.at(spanning_edge) != Edge::Unknown) {
      edges.at(backedge) = edges.at(spanning_edge);
    } else if (edges.at(backedge) != Edge::Unknown) {
      edges.at(spanning_edge) = edges.at(backedge);
    }
  }

  current_golden.at(spanning_edge_i) = spanning_edge;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) { // NOLINT
  vector<TreeNode> tree = build_tree(n, u, v);
  vector<Backedge> backedges = get_backedges(tree);
  vector<Edge> edges(u.size(), Edge::Unknown);

  vector<int> current_golden = get_initial(tree);
  sort(current_golden.begin(), current_golden.end());

  // cout << "\n\nASKING NOW\n\n";

  int init_res = count_common_roads(current_golden);

  for (const Backedge &backedge : backedges) {
    for (int spanning_edge : backedge.spanning_edges) {
      if (edges.at(spanning_edge) == Edge::Unknown ||
          edges.at(backedge.id) == Edge::Unknown) {
        test_by_cycle(spanning_edge, current_golden, edges, backedge.id,
                      init_res);
      }
    }

    // equivalences
    // if (edges.at(backedge.id) != Edge::Unknown) { // i think this MUST happen
    // :(
    // }
    for (int spanning_edge : backedge.spanning_edges) {
      if (edges.at(spanning_edge) == Edge::Unknown) {
        edges.at(spanning_edge) = edges.at(backedge.id);

        if (edges.at(backedge.id) == Edge::Present) {
          // cout << "setting " << spanning_edge << " to present\n";
        }
        if (edges.at(backedge.id) == Edge::Absent) {
          // cout << "setting " << spanning_edge << " to absent\n";
        }
      }
    }
  }

  vector<int> answer;
  for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
    if (edges.at(i) == Edge::Absent) {
      continue;
    }
    answer.push_back(i);
  }
  return answer;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 360 KB correct
6 Incorrect 0 ms 348 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 360 KB correct
6 Incorrect 0 ms 348 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 360 KB correct
6 Incorrect 0 ms 348 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 123 ms 50100 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 360 KB correct
6 Incorrect 0 ms 348 KB WA in grader: NO
7 Halted 0 ms 0 KB -