제출 #1252724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252724		flashmt	World Map (IOI25_worldmap)	C++20	86 / 100	44 ms	3912 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);

  // trim unnecessary backward edges
  while (size(path) >= 2)
  {
    int x = path[size(path) - 2], y = path[size(path) - 1];
    if (depth[x] < depth[y])
      break;
    path.pop_back();
  }

  for (int i = 0; i + 1 < size(path); i++)
  {
    int x = path[i], y = path[i + 1];
    adj[x][y] = adj[y][x] = 0;
  }

  int len = size(path);
  vector<int> isDummy(len), seen(n);
  for (int i = 0; i < size(path); i++)
  {
    int x = path[i];
    if (!seen[x])
    {
      for (int j = 0; j < i; j++)
      {
        int y = path[j];
        if (adj[x][y])
          adj[x][y] = 0;
      }

      int hasEdge = 0;
      for (int y = 0; y < n; y++)
        hasEdge |= adj[x][y];

      if (!hasEdge) isDummy[i] = 1;
      else seen[x] = 1;
    }
    else isDummy[i] = 1;
  }

  int colNeed = 0;
  for (int i = 0; i < len; i++)
    if (isDummy[i]) colNeed++;
    else colNeed += 2;

  int k = max(n * 2, colNeed);
  debug(path); debug(isDummy); debug(k);
  vector<vector<int>> ans(k, vector<int>(k, -1));
  for (int i = 0, parity = 0, col = 0; i < len; i++)
  {
    int x = path[i];
    if (isDummy[i])
    {
      for (int row = 0; row < k; row++)
        if (parity) ans[row][col - 1 + row % 2] = x;
        else ans[row][col - row % 2] = x;
      col++;
      continue;
    }

    if (parity == 0)
    {
      for (int row = 0; row < k; row++)
        if (row % 2 == 0) ans[row][col] = x;
        else
        {
          ans[row][col + 1] = x;
          if (col)
            ans[row][col - 1] = x;
        }

      for (int row = 1; row < k; row += 2)
        ans[row][col] = row / 2 < n && adj[x][row / 2] ? row / 2 : x;
    }
    else
    {
      for (int row = 0; row < k; row++)
        if (row % 2) ans[row][col] = x;
        else ans[row][col - 1] = ans[row][col + 1] = x;

      for (int row = 0; row < k; row += 2)
        ans[row][col] = row / 2 < n && adj[x][row / 2] ? row / 2 : x;
    }

    parity ^= 1;
    col += 2;
  }

  for (int i = 0; i < k; i++)
    for (int &x : ans[i])
      if (x < 0) x = path.back() + 1;
      else x++;

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