제출 #1249381

#제출 시각아이디문제언어결과실행 시간메모리
1249381model_codeWorld Map (IOI25_worldmap)C++20
100 / 100
24 ms2932 KiB
// sub6-2k.cpp #include "worldmap.h" #include <vector> #include <iostream> using namespace std; std::vector<std::vector<int> > create_map(int N, int M, std::vector<int> A, std::vector<int> B) { // step #1. preparation vector<vector<int> > G(N); for (int i = 0; i < M; i++) { A[i]--; B[i]--; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } // step #2. make spanning tree vector<bool> vis(N, false); vector<int> depth(N); vector<int> tour, RA, RB; auto dfs = [&](auto& self, int x) -> void { vis[x] = true; tour.push_back(x); for (int i : G[x]) { if (!vis[i]) { depth[i] = depth[x] + 1; self(self, i); tour.push_back(x); } else if (depth[x] < depth[i]) { RA.push_back(x); RB.push_back(i); } } }; dfs(dfs, 0); // step #3. construction vector<int> rank(N, -1), holder(N, -1); for (int i = 0; i < 2 * N - 1; i++) { int d = min(i, (2 * N - 2) - i); if (rank[tour[i]] < d) { rank[tour[i]] = d; holder[tour[i]] = i; } } vector<vector<int> > H(N); for (int i = 0; i < M - (N - 1); i++) { if (rank[RA[i]] < rank[RB[i]]) { swap(RA[i], RB[i]); } H[RA[i]].push_back(RB[i]); } vector<vector<int> > ans(2 * N, vector<int>(2 * N, 0)); int cur = 0, parity = 0; for (int i = 0; i < 2 * N - 1; i++) { if (i == holder[tour[i]]) { int pos = 0; for (int j = 0; j < 2 * N; j++) { int ya = cur - j; if (0 <= ya && ya < 2 * N) { ans[j][ya] = tour[i]; } int yb = (cur + 1) - j; if (0 <= yb && yb < 2 * N) { if (pos < int(H[tour[i]].size())) { ans[j][yb] = H[tour[i]][pos]; pos++; } else { ans[j][yb] = tour[i]; } } int yc = (cur + 2) - j; if (0 <= yc && yc < 2 * N) { ans[j][yc] = tour[i]; } } cur += 3; parity ^= 1; } else { for (int j = 0; j < 2 * N; j++) { int ya = cur - j; if (0 <= ya && ya < 2 * N) { ans[j][ya] = tour[i]; } } cur += 1; } } // step #4. final step for (int i = 0; i < int(ans.size()); i++) { for (int j = 0; j < int(ans.size()); j++) { ans[i][j]++; } } return 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...