제출 #1271496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271496		strange420	World Map (IOI25_worldmap)	C++20	29 / 100	23 ms	2888 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>>& adj_matrix) {
  std::vector<std::vector<int>> edges(adj_list.size());
  for (int i=0; i<adj_list.size(); i++) {
    edges[i].resize(adj_list.size(), 0);
  }

  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])
        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<std::vector<int>>& adj_matrix) {
  std::vector<int> spanning_path = spanning_tree(adj_list, adj_matrix);
  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), adj_matrix(N+1, std::vector<int>(N+1, 0));
  for (int i=0; i<M; i++) {
    adj_list[A[i]].push_back(B[i]);
    adj_list[B[i]].push_back(A[i]);
    adj_matrix[A[i]][B[i]] = adj_matrix[B[i]][A[i]] = 1;
  }

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

  // 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 14 / 14
• Subtask 6: 0 / 56