제출 #1258074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258074		avighna	World Map (IOI25_worldmap)	C++20	15 / 100	1071 ms	2162688 KiB

worldmap

#include <bits/stdc++.h>

std::vector<std::vector<int>> adj;

std::vector<std::vector<int>> dfs(int u, int p) {
  std::vector<std::vector<std::vector<int>>> children;
  int max_size = 0, sum_width = 0, num_children = 0;
  for (int &i : adj[u]) {
    if (i == p) {
      continue;
    }
    children.push_back(dfs(i, u));
    max_size = std::max(max_size, int(children.back().size()));
    sum_width += children.back()[0].size();
    num_children++;
  }
  if (num_children == 0) {
    return {{u}};
  }
  for (auto &i : children) {
    while (i.size() < max_size) {
      i.push_back(i.back());
    }
  }
  std::vector ans(max_size + 1,
                  std::vector<int>(sum_width + num_children + 1, u));
  int start = 1;
  for (auto &ch : children) {
    for (int i = 0; i < ch.size(); ++i) {
      for (int j = 0; j < ch[i].size(); ++j) {
        ans[i + 1][start + j] = ch[i][j];
      }
    }
    start += ch[0].size() + 1;
  }
  return ans;
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A,
                                         std::vector<int> B) {
  adj.clear();
  adj.resize(N + 1);
  for (int i = 0; i < M; ++i) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  auto ans = dfs(1, 0);
  if (ans.size() <= ans[0].size()) {
    while (ans.size() < ans[0].size()) {
      ans.push_back(ans.back());
    }
  } else {
    int old = ans[0].size();
    for (auto &i : ans) {
      i.resize(ans.size());
      for (int j = old + 1; j < i.size(); ++j) {
        i[j] = i[j - 1];
      }
    }
  }
  return ans;
}

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