Submission #1271467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271467		strange420	World Map (IOI25_worldmap)	C++20	0 / 100	4 ms	1096 KiB

worldmap

#include "worldmap.h"
#include <algorithm>
#include <iostream>
#include <functional>
#include <utility>
#include <cmath>

std::vector<int> spanning_tree(std::vector<std::vector<int>>& adj_list) {
  std::vector<std::vector<int>> edges(adj_list.size());
  std::vector<std::vector<int>> adj_matrix(adj_list.size()); 
  for (int i=0; i<adj_list.size(); i++) {
    edges[i].resize(adj_list.size(), 0);
    adj_matrix[i].resize(adj_list.size(), 0);
  }
  for (int i=0; i<adj_list.size(); i++) {
    for (int j: adj_list[i]) {
      adj_matrix[i][j] = 1;
      adj_matrix[j][i] = 1;
    }
  }

  std::function<bool(int, int)> dfs;
  std::vector<int> visited(adj_list.size(), 0), path;
  dfs = [&](int u, int p) {
    if (visited[u]) return false;
    visited[u] = 1;

    path.push_back(u);
    edges[u][p] = edges[p][u] = 1;
    adj_matrix[u][p] = adj_matrix[p][u] = 0;

    for (int v: adj_list[u])
      if (dfs(v, u)) path.push_back(u);
    return true;
  }; dfs(1, 0);

  // Remove redundant path
  int i=path.size()-2;
  for (; path[i+1] != path[i-1]; i--) {}
  path.resize(i+1);

  std::vector<std::vector<int>> new_adj_list(adj_list.size());
  for (int i=0; i<adj_matrix.size(); i++)
    for (int j=0; j<adj_matrix.size(); j++)
      if (adj_matrix[i][j] && i < j)
        new_adj_list[i].push_back(j);
  adj_list = new_adj_list;
  
  return path;
}

std::vector<int> get_path(std::vector<std::vector<int>>& adj_list) {
  std::vector<int> spanning_path = spanning_tree(adj_list);
  for (int i=0; i<adj_list.size(); i++) {
    for (int j: adj_list[i]) {
      bool flag = false;
      std::vector<int> new_path;
      for (int k: spanning_path) {
        new_path.push_back(k);
        if (flag) continue;
        if (k == i) {
          flag = true;
          new_path.push_back(j);
          new_path.push_back(i);
        } else if (k == j) {
          flag = true;
          new_path.push_back(i);
          new_path.push_back(j);
        }
      }
      spanning_path = new_path;
    }
  }
  return spanning_path;
}

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

  std::vector<int> partial = get_path(adj_list);

  // Diagonalization
  int K = (partial.size() + 1) / 2;
  std::vector<std::vector<int>> ans(K);
  for (int i=0; i<K; i++) {
    for (int j=0; j<K; j++) {
      ans[i].push_back(partial[i+j]);
    }
  }
  return ans;
}

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