Submission #1251417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251417		gangsterveggies	World Map (IOI25_worldmap)	C++20	72 / 100	57 ms	7492 KiB

worldmap

#include "worldmap.h"
#include <functional>

using namespace std;

// Helper function to find a sequence of integers satisfying the conditions
  std::vector<int> find_sequence(int N, const std::vector<std::vector<int>>& adjacency_list) {
    std::vector<int> sequence;
    std::vector<bool> visited(N, false);
    std::function<void(int)> dfs = [&](int node) {
      visited[node] = true;
      sequence.push_back(node);
      for (int neighbor : adjacency_list[node]) {
        if (visited[neighbor]) continue;
        dfs(neighbor);
        sequence.push_back(node);
      }
    };
    dfs(0);
    return sequence;
  }

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  if (N == 1) {
    return {{1}};
  }

  std::vector<std::vector<int>> adjacency_list(N);
  for (int i = 0; i < M; ++i) {
    adjacency_list[A[i] - 1].push_back(B[i] - 1);
    adjacency_list[B[i] - 1].push_back(A[i] - 1);
  }

  std::vector<int> sequence = find_sequence(N, adjacency_list);
  std::vector<int> first_occurrence(sequence.size(), 0);
  std::vector<bool> seen(N, false);
  for (size_t i = 0; i < sequence.size(); ++i) {
    if (!seen[sequence[i]]) {
      first_occurrence[i] = 1;
      seen[sequence[i]] = true;
    }
  }

  for (int i = first_occurrence.size() - 1; i >= 0; --i) {
    if (first_occurrence[i]) {
      sequence.resize(i + 1);
      first_occurrence.resize(i + 1);
      break;
    }
  }

  std::vector<std::vector<int>> ans;

  for (int i = 0; i < sequence.size(); ++i) {
    int node = sequence[i];
    if (first_occurrence[i]) {
      std::vector<int> neighbors;
      for (int neighbor : adjacency_list[node]) {
        if (neighbor > node) {
          neighbors.push_back(neighbor + 1);
          neighbors.push_back(node + 1);
        }
      }
      if (!neighbors.empty()) {
        neighbors.pop_back();
      }

      ans.push_back({node + 1});
      if (!neighbors.empty()) {
        ans.push_back(neighbors);
        ans.push_back({node + 1});
      }
    } else {
      ans.push_back({node + 1});
    }
  }

  ans.pop_back();

  int mx_len = ans.size();
  for (int i = 0; i < ans.size(); ++i) {
    if (ans[i].size() > mx_len) {
      mx_len = ans[i].size();
    }
  }

  for (int i = 0; i < ans.size(); ++i) {
    int last = ans[i].back();
    while (ans[i].size() < mx_len) {
      ans[i].push_back(last);
    }
  }

  while (ans.size() < mx_len) {
    ans.push_back(ans.back());
  }

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 28 / 56