Submission #1252783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252783		flashmt	세계 지도 (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int N = 44;

vector<int> a[N];
int depth[N];

void dfs(int x, vector<int> &path)
{
  path.push_back(x);
  for (int y : a[x])
    if (depth[y] < 0)
    {
      depth[y] = depth[x] + 1;
      dfs(y, path);
      path.push_back(x);
    }
}

vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
  for (int &x : A)
    x--;
  for (int &x : B)
    x--;
  for (int i = 0; i < n; i++)
  {
    a[i].clear();
    depth[i] = -1;
  }

  vector<vector<int>> adj(n, vector<int>(n));
  for (int i = 0; i < m; i++)
  {
    a[A[i]].push_back(B[i]);
    a[B[i]].push_back(A[i]);
    adj[A[i]][B[i]] = adj[B[i]][A[i]] = 1;
  }

  vector<int> path;
  depth[0] = 0;
  dfs(0, path);

  vector<int> sz(n * 4);
  for (int i = 0; i < n * 2; i++)
    for (int j = 0; j < n * 2; j++)
      sz[i + j]++;

  vector<int> diagonals, neighborDia(n, -1);
  vector<pair<int, int>> neighborOrder;
  for (int x : path)
  {
    if (neighborDia[x] < 0)
    {
      diagonals.push_back(x);
      diagonals.push_back(x + n);
      neighborDia[x] = size(diagonals) - 1;
      neighborOrder.push_back({sz[neighborDia[x]], x});
    }
    diagonals.push_back(x);
  }
  while (size(diagonals) < n * 4 - 1)
    diagonals.push_back(path.back());

  sort(begin(neighborOrder), end(neighborOrder));
  vector<int> rank(n);
  for (int i = 0; i < size(neighborOrder); i++)
    rank[neighborOrder[i].second] = i;

  vector<vector<int>> ans(n * 2, vector<int>(n * 2));
  for (int d = 0; d < n * 4 - 1; d++)
  {
    int x = diagonals[d];
    vector<pair<int, int>> cells;
    for (int i = 0; i < n * 2; i++)
    {
      int j = d - i;
      if (0 <= j && j < n * 2)
        cells.push_back({i, j});
    }

    if (x < n)
    {
      for (auto [i, j] : cells)
        ans[i][j] = x + 1;
    }
    else
    {
      x -= n;
      vector<int> neighbors;
      for (int y = 0; y < n; y++)
        if (rank[y] < rank[x] && adj[x][y])
          neighbors.push_back(y);

      assert(size(neighbors) <= size(cells));
      for (int k = 0; k < size(cells); k++)
      {
        auto [i, j] = cells[k];
        if (k < size(neighbors)) ans[i][j] = neighbors[k] + 1;
        else ans[i][j] = x + 1;
      }
    }
  }

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