제출 #1251186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251186		aryan12	세계 지도 (IOI25_worldmap)	C++20	5 / 100	34 ms	4676 KiB

worldmap

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

const int MAXN = 55;
vector<int> dfs_order;
vector<int> g[MAXN], allg[MAXN];
int par[MAXN];

int find(int x) {
  if(x == par[x]) return x;
  return par[x] = find(par[x]);
}

void unite(int x, int y) {
  x = find(x);
  y = find(y);
  par[y] = x;
}

void dfs(int node, int par) {
  dfs_order.push_back(node);
  for(int to: g[node]) {
    if(to == par) continue;
    dfs(to, node);
    dfs_order.push_back(node);
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  if(N == 1) {
    return {{1}};
  }
  for(int i = 0; i <= N; i++) {
    par[i] = i;
    g[i].clear();
    allg[i].clear();
  }
  dfs_order.clear();
  for(int i = 0; i < M; i++) {
    allg[A[i]].push_back(B[i]);
    allg[B[i]].push_back(A[i]);
    if(find(A[i]) != find(B[i])) {
      g[A[i]].push_back(B[i]);
      g[B[i]].push_back(A[i]);
      unite(A[i], B[i]);
    }
  }
  dfs(1, -1);

  vector<vector<int> > the_map(4 * N, vector<int> (4 * N, 0));
  int cur = 0;
  for(int diagonal_sum = 0; diagonal_sum <= 8 * N; diagonal_sum++) {
    cur = min(cur, (int)dfs_order.size() - 1);
    if(diagonal_sum < 2 * N || diagonal_sum > 6 * N) {
      for(int i = 0; i <= diagonal_sum; i++) {
        int j = diagonal_sum - i;
        if(i > 4 * N - 1 || j > 4 * N - 1) continue;
        the_map[i][j] = dfs_order[cur];
      }
      continue;
    }
    if((diagonal_sum - N) % 3 != 1) {
      for(int i = 0; i <= diagonal_sum; i++) {
        int j = diagonal_sum - i;
        if(i > 4 * N - 1 || j > 4 * N - 1) continue;
        the_map[i][j] = dfs_order[cur];
      }
    }
    else {
      int omk = 0, curr = 0;
      for(int i = 0; i <= diagonal_sum; i++) {
        int j = diagonal_sum - i;
        if(i > 4 * N - 1 || j > 4 * N - 1) continue;
        if(omk & 1) {
          the_map[i][j] = dfs_order[cur];
        }
        else {
          the_map[i][j] = allg[dfs_order[cur]][curr];
          curr = min(curr + 1, (int)allg[dfs_order[cur]].size() - 1);
        }
        omk ^= 1;
      }
    }

    if((diagonal_sum - N) % 3 == 2) {
      cur += 1;
    }
  }
  return the_map;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56