제출 #1256745

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

worldmap

#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

void getOrder(vector<int> &order, vector<bool> &vis, int i, vector<vector<int>> edges) {
  if (vis[i]) return;
  vis[i] = true;
  for (int j : edges[i]) {
    if (vis[j]) continue;
    order.push_back(i);
    getOrder(order, vis, j, edges);
  }
  order.push_back(i);
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  vector<vector<int>> edges(N);
  for (int i = 0; i < M; i++) {
    edges[A[i] - 1].push_back(B[i] - 1);
    edges[B[i] - 1].push_back(A[i] - 1);
  }
  vector<int> order;
  vector<bool> vis(N);
  getOrder(order, vis, 0, edges);
  for (int i = 0; i < N; i++) vis[i] = false;
  vector<vector<int>> ans(floor(2.5 * N), vector<int>(floor(2.5 * N), 0));
  int cur = 0;
  int phase = 0;
  for (int i = N - 2; i < floor(2.5 * N) && cur < order.size(); i++) {
    if (vis[order[cur]] && phase == 1) {
      cur++;
      phase = 0;
      i--;
      continue;
    }
    if (phase == 0 || phase == 2) {
      int x = 0;
      int y = i;
      while (y >= 0) {
        ans[x][y] = order[cur];
        x++;
        y--;
      }
      phase++;
      if (phase == 3) {
        cur++;
        phase = 0;
      }
    }
    else if (phase == 1) {
      vis[order[cur]] = true;
      int x = 0;
      int y = i;
      int ind = 0;
      while (y >= 0) {
        if (ind < edges[order[cur]].size()) {
          if (vis[edges[order[cur]][ind]]) {
            ind++;
            continue;
          }
          ans[x][y] = edges[order[cur]][ind++];
        }
        else ans[x][y] = order[cur];
        x++;
        y--;
      }
      phase++;
    }
  }
  for (int i = 1; i < floor(2.5 * N) && cur < order.size(); i++) {
    if (vis[order[cur]] && phase == 1) {
      cur++;
      phase = 0;
      i--;
      continue;
    }
    if (phase == 0 || phase == 2) {
      int x = i;
      int y = floor(2.5 * N) - 1;
      while (x < floor(2.5 * N)) {
        ans[x][y] = order[cur];
        x++;
        y--;
      }
      phase++;
      if (phase == 3) {
        cur++;
        phase = 0;
      }
    }
    else if (phase == 1) {
      vis[order[cur]] = true;
      int x = i;
      int y = floor(2.5 * N) - 1;
      int ind = 0;
      while (x < floor(2.5 * N)) {
        if (ind < edges[order[cur]].size()) {
          if (vis[edges[order[cur]][ind]]) {
            ind++;
            continue;
          }
          ans[x][y] = edges[order[cur]][ind++];
        }
        else ans[x][y] = order[cur];
        x++;
        y--;
      }
      phase++;
    }
  }
  for (int i = 0; i < floor(2.5 * N); i++) {
    for (int j = 0; j < floor(2.5 * N); j++) {
      ans[i][j]++;
    }
  }
  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: 49 / 56