제출 #1251588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251588		aryan12	세계 지도 (IOI25_worldmap)	C++20	15 / 100	33 ms	4420 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);

  // cerr << "dfs order" << endl;
  // for(int x: dfs_order) {
  //   cerr << x << " ";
  // }
  // cerr << endl;

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

    if(diagonal_sum % 3 == 2 && max_curr == (int)allg[dfs_order[cur]].size() - 1) {
      cur += 1;
      curr = 0;
      max_curr = 0;
    }
  }
  return the_map;
}

• 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