Submission #1253316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253316		Gabp	World Map (IOI25_worldmap)	C++20	72 / 100	89 ms	8260 KiB

worldmap

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
  if (n == 1) {
    return {{1}};
  }
  
  vector<vector<int>> g(n);
  vector<vector<bool>> done(n, vector<bool>(n, true));
  for (int i = 0; i < m; i++) {
    a[i]--; b[i]--;
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
    done[a[i]][b[i]] = done[b[i]][a[i]] = false;
  }
  vector<bool> vis(n, false);
  
  vector<int> order;
  auto dfs = [&](auto self, int root) -> void {
    vis[root] = true;
    order.push_back(root);
    
    for (auto v: g[root]) {
      if (vis[v]) continue;
      self(self, v);
      done[root][v] = done[v][root] = true;
      order.push_back(root);
    }
  };
  dfs(dfs, 0);
  
  int k = order.size();
  vector<vector<int>> ans;
  for (int i = 0; i < order.size(); i++) {
    bool need = false;
    int id = order[i];
    for (auto v: g[id]) {
      if (!done[v][id]) need = true;
    }
    
    if (need) {
      if (i) ans.push_back(vector<int>(1, id));
      ans.push_back(vector<int>());
      for (auto v: g[id]) {
        if (done[v][id]) continue;
        if (!ans.back().empty()) ans.back().push_back(id);
        ans.back().push_back(v);
        done[v][id] = done[id][v] = true;
      }
      k = max(k, (int)ans.back().size());
    }
    
    if (i + 1 < order.size()) {
      ans.push_back(vector<int>(1, id));
    }
  }
  k = max(k, (int)ans.size());
  
  if (ans.size() < k) {
    int id;
    if (ans.back().size() == 1) id = ans.back()[0];
    else id = ans.back()[1];
    while (ans.size() < k) {
      ans.push_back(vector<int>(k, id));
    }
  }
  
  for (int i = 0; i < k; i++) {
    int id;
    if (ans[i].size() == 1) id = ans[i][0];
    else id = ans[i][1];
    while (ans[i].size() < k) ans[i].push_back(id);
    for (int j = 0; j < k; j++) ans[i][j]++;
  }
  
  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