제출 #1249769

#제출 시각아이디문제언어결과실행 시간메모리
1249769QwertyPi세계 지도 (IOI25_worldmap)C++20
0 / 100
2 ms580 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; const int N_MAX = 40 + 11; vector<int> G[N_MAX], adj[N_MAX]; vector<vector<int>> regulate(vector<vector<int>> board) { int n = board.size(), m = board[0].size(); int K = max(n, m); vector ans = vector(K, vector<int>(K)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ans[i][j] = board[i][j]; } } for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { if (!ans[i][j]) { if (j > 0 && ans[i][j - 1]) ans[i][j] = ans[i][j - 1]; else if (i > 0 && ans[i - 1][j]) ans[i][j] = ans[i - 1][j]; else assert(false); } } } return ans; } bool vis[N_MAX]; int sz[N_MAX], dep[N_MAX]; vector<int> ch[N_MAX]; void dfs0(int v, int pa = -1) { vis[v] = true; sz[v] = 1; ch[v].clear(); for (int u : G[v]) { if (vis[u]) continue; ch[v].push_back(u); dep[u] = dep[v] + 1; dfs0(u, v); sz[v] += sz[u]; } } vector<vector<int>> ans; void paint(int x, int y, int c) { if (x < 0 || x >= ans.size() || y < 0 || y >= ans[0].size()) return; ans[x][y] = c; } void paint2(int x, int y, int c1, int c2) { paint(x, y, c1); for (auto [dx, dy] : vector<pair<int, int>>{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) { paint(x + dx, y + dy, c2); } } int _N; void dfs(int v, int pa, int x = 0, int y = 0, bool is_last = true) { cout << "DFS " << v << ' ' << pa << ' ' << x << ' ' << y << endl; vis[v] = true; for (int i = 0; i < (is_last ? _N - y / 2: sz[v] - 1); i++) { // paint(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v); paint2(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v, v); } int lst = ch[v].empty() ? -1 : ch[v].back(); for (int u : G[v]) { if (vis[u]) continue; dfs(u, v, x + 2, y, u == lst); y += sz[u] * 2; if (u != lst) { for (int i = x + 2; i < _N * 2; i++) { paint(i, y + (x % 4 / 2) - 2, v); } } } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { _N = N; for (int i = 1; i <= N; i++) { G[i].clear(); adj[i].clear(); } fill(vis, vis + N + 1, false); for (int i = 0; i < M; i++) { G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } // for (int i = 1; i <= N; i++) { // cout << "G[" << i << "] => "; for (auto x : G[i]) cout << x << ' '; cout << endl; // } dfs0(1); for (int i = 0; i < M; i++) { if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]); adj[A[i]].push_back(B[i]); } ans = vector(N * 2, vector<int> (N * 2)); fill(vis, vis + N + 1, false); dfs(1, -1); return regulate(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...