Submission #1250029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250029		flashmt	World Map (IOI25_worldmap)	C++20	15 / 100	15 ms	2120 KiB

worldmap

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

struct DisjointSet
{
  int n;
  vector<int> ds, sz;

  DisjointSet(int n): n(n)
  {
    ds = sz = vector<int>(n);
    for (int i = 0; i < n; i++)
    {
      ds[i] = i;
      sz[i] = 1;
    }
  }

  int get(int x)
  {
    return x == ds[x] ? x : ds[x] = get(ds[x]);
  }

  int join(int x, int y)
  {
    int dx = get(x), dy = get(y);
    if (dx == dy)
      return 0;
    if (sz[dx] < sz[dy])
      swap(dx, dy);
    ds[dy] = dx;
    sz[dx] += sz[dy];
    return 1;
  }
};

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;
  }

  DisjointSet ds(n);
  vector<vector<int>> adj(n, vector<int>(n));
  for (int i = 0; i < m; i++)
  {
    if (ds.join(A[i], B[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();
  }

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

  vector<int> hasNonPathEdges(n);
  hasNonPathEdges[path[0]] = 1;
  int colNeed = n;
  for (int x = 0; x < n; x++)
  {
    for (int y = x + 1; y < n; y++)
      hasNonPathEdges[x] |= adj[x][y];
    colNeed += hasNonPathEdges[x];
  }
  debug(hasNonPathEdges); debug(colNeed);

  int k = max(n * 2, colNeed);
  debug(path); debug(k);
  vector<int> seen(n);
  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 (seen[x] || !hasNonPathEdges[x])
    {
      debug(x, "dummy");
      if (parity)
      {
        for (int row = 0; row < k; row++)
          ans[row][col - 1 + row % 2] = x;
      }
      else
      {
        for (int row = 0; row < k; row++)
          ans[row][col - row % 2] = x;
      }
      col++;
      continue;
    }

    debug(x, "real");
    seen[x] = 1;
    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 y = 0; y < k / 2; y++)
        ans[y * 2 + 1][col] = y < n && adj[x][y] ? y : 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 y = 0; y < k / 2; y++)
        ans[y * 2][col] = y < n && adj[x][y] ? y : 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: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56