Submission #1249702

#TimeUsernameProblemLanguageResultExecution timeMemory
1249702QwertyPi세계 지도 (IOI25_worldmap)C++20
72 / 100
74 ms9416 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; const int N_MAX = 40 + 11; vector<int> G[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); } } } // for (int i = 0; i < K; i++) { // for (int j = 0; j < K; j++) { // cout << ans[i][j] << ' '; // } // cout << '\n'; // } return ans; } bool vis[N_MAX]; vector<pair<int, bool>> st; void dfs(int v, int pa = -1) { vis[v] = true; for (int u : G[v]) { if (vis[u]) continue; st.push_back({u, true}); dfs(u, v); st.push_back({v, false}); } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { for (int i = 1; i <= N; i++) { G[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]); } st = vector<pair<int, bool>>{{1, true}}; dfs(1); vector ans = vector(N * 3 + (N - 1), vector<int> (N * 2)); int x = 0; for (auto [v, fi] : st) { if (fi) { for (int j = 0; j < 3; j++) { for (int k = 0; k < N * 2; k++) { ans[x + j][k] = v; } } for (int j = 0; j < G[v].size(); j++) { ans[x + 1][j * 2] = G[v][j]; } x += 3; } else { for (int k = 0; k < N * 2; k++) { ans[x][k] = v; } x++; } } 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...