제출 #1249490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249490		_is_this_fft_	World Map (IOI25_worldmap)	C++20	100 / 100	25 ms	2884 KiB

worldmap

#include "worldmap.h"
#include <vector>

using namespace std;

struct Graph {
  int n;
  vector<vector<int>> adj;
  vector<vector<int>> ch; // child in dfs tree
  vector<int> lvl;
  vector<int> w;
  vector<vector<int>> back_dn; // back-edges down

  Graph (int _n) : n(_n),
                   adj(_n, vector<int> (0)),
                   ch(_n, vector<int> (0)),
                   lvl(_n, 0),
                   w(_n, 0),
                   back_dn(_n, vector<int> (0)) { }

  void add_edge (int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  void dfs (int u, int p) {
    lvl[u] = lvl[p] + 1;
    w[u] = 0;
    
    for (int nxt : adj[u]) {
      if (lvl[nxt] == 0) {
        ch[u].push_back(nxt);
        dfs(nxt, u);
        w[u] += w[nxt];
      } else if (lvl[nxt] > lvl[u]) {
        back_dn[u].push_back(nxt);
      }
    }

    if (ch[u].empty()) {
      w[u] = 1;
    } else {
      w[u] += 1 + ch[u].size();
    }
  }
};

struct Canvas {
  int k;
  vector<vector<int>> grid;

  Canvas (int _k, int init) : k(_k), grid(_k, vector<int> (_k, init)) { }

  void fill_teeth (int x1, int x2, int y1, int y2, int c) {
    for (int j = y1; j < y2; j += 2)
      grid[x1][j] = c;

    for (int i = x1 + 1; i < x2; i++) {
      for (int j = y1; j < y2; j++) {
        grid[i][j] = c;
      }
    }
  }
  
  void fill (int x1, int x2, int y1, int y2, int c) {
    for (int i = x1; i < x2; i++) {
      for (int j = y1; j < y2; j++) {
        grid[i][j] = c;
      }
    }
  }

  void dot (int x, int y, int c) {
    grid[x][y] = c;
  }
};

void draw (int u, int x1, int x2, int y1, int y2, Canvas &C, const Graph &G) {
  C.fill_teeth(x1, x2, y1, y2, u);

  int bey = y1 + 2;
  for (int v : G.back_dn[u]) {
    C.dot(x1 + 1, bey, v);
    bey += 2;
  }

  int chy = y1 + 1;
  for (int v : G.ch[u]) {
    draw(v, x1 + 2, x2, chy, chy + G.w[v], C, G);
    chy += G.w[v] + 1;
  }
}

vector<vector<int>> create_map (int n, int m, vector<int> A, vector<int> B) {
  Graph G (n + 1);
  for (int i = 0; i < m; i++) {
    G.add_edge(A[i], B[i]);
  }

  G.dfs(1, 1);
  Canvas C (2 * n, 1);
  draw(1, 0, C.k, 0, C.k, C, G);

  return C.grid;
}

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