Submission #1260831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260831		avighna	World Map (IOI25_worldmap)	C++20	100 / 100	27 ms	2884 KiB

worldmap

#include <bits/stdc++.h>

std::vector<std::vector<int>> adj;
std::vector<bool> vis;
std::set<std::pair<int, int>> edges;
std::vector<int> depth;

std::vector<std::vector<int>> dfs(int u, int p) {
  edges.erase({u, p});
  edges.erase({p, u});
  vis[u] = true;
  std::vector<std::vector<std::vector<int>>> children;
  int max_size = 0, sum_width = 0, num_children = 0;
  for (int &i : adj[u]) {
    if (vis[i]) {
      continue;
    }
    depth[i] = depth[u] + 1;
    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}, {u}};
  }
  for (auto &i : children) {
    while (int(i.size()) < max_size) {
      i.push_back(i.back());
    }
  }
  std::vector ans(max_size + 2, std::vector<int>(sum_width + num_children + 1, u));
  int start = 1;
  for (auto &ch : children) {
    for (int i = 0; i < int(ch.size()); ++i) {
      for (int j = 0; j < int(ch[i].size()); ++j) {
        ans[i + 2][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(), vis.clear(), edges.clear(), depth.clear();
  adj.resize(N + 1), vis.resize(N + 1), depth.resize(N + 1);
  for (int i = 0; i < M; ++i) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
    edges.insert({A[i], B[i]});
  }
  auto a = dfs(1, 0);
  std::vector<int> upsert_row(N + 1, a.size()), upsert_col(N + 1);
  for (int i = 0; i < int(a.size()) - 1; ++i) {
    for (int j = 0; j < int(a[i].size()); ++j) {
      if (a[i][j] == a[i + 1][j]) {
        upsert_row[a[i][j]] = std::min(upsert_row[a[i][j]], i + 1);
      }
    }
  }
  for (int i = 1; i <= N; ++i) {
    upsert_col[i] = std::find(a[upsert_row[i]].begin(), a[upsert_row[i]].end(), i) - a[upsert_row[i]].begin() + 1;
  }
  for (auto [src, to] : edges) {
    // to will always be an ancestor/child of src due to the dfs tree
    if (depth[to] > depth[src]) {
      std::swap(src, to);
    }
    int x = upsert_row[to], y = upsert_col[to];
    a[x][y] = src, a[x + 1][y] = to;
    upsert_col[to] += 2;
  }
  if (a.size() <= a[0].size()) {
    while (a.size() < a[0].size()) {
      a.push_back(a.back());
    }
  } else {
    int old = a[0].size();
    for (auto &i : a) {
      i.resize(a.size());
      for (int j = old; j < int(i.size()); ++j) {
        i[j] = i[j - 1];
      }
    }
  }
  return a;
}

• 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: 56 / 56