Submission #1250573

#TimeUsernameProblemLanguageResultExecution timeMemory
1250573ogkostyaWorld Map (IOI25_worldmap)C++20
100 / 100
22 ms2888 KiB
#include "worldmap.h" #include <cstdio> bool ff[100][100]; bool f[100]; std::vector<std::vector<int>> ans; std::pair<int, std::pair<int, int>> order[100]; int height(int i, int n) { if (i < 2 * n) return i + 1; return 4 * n - i; } void dfs(int to, int from, int N) { f[to] = true; ans.push_back(std::vector<int>(2 * N, to)); order[to - 1] = std::pair(height(ans.size(), N), std::pair(ans.size(), to)); ans.push_back(std::vector<int>(2 * N, to)); ans.push_back(std::vector<int>(2 * N, to)); for (int i = 1; i <= N; i++) { if (ff[to][i] && !f[i]) { ff[to][i] = false; ff[i][to] = false; dfs(i, to, N); } } if (to != from) ans.push_back(std::vector<int>(2 * N, from)); } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { if (N == 1) { return {{1}}; } if (N == 2) { return {{1, 2}, {1, 2}}; } std::fill(&ff[0][0], &ff[0][0] + sizeof(ff), false); for (int i = 0; i < M; i++) { ff[A[i]][B[i]] = true; ff[B[i]][A[i]] = true; } std::fill(f, f + 100, false); std::fill(order, order + 100, std::pair(0, std::pair(0, 0))); ans.clear(); dfs(1, 1, N); std::sort(order, order + N); std::reverse(order, order + N); for (int j = 0; j < N; j++) { int to = order[j].second.second; int index = order[j].second.first; for (int i = 1, k = 0; i <= N; i++) { if (ff[to][i]) { ff[to][i] = false; ff[i][to] = false; ans[index][k++] = i; } } } std::vector<std::vector<int>> ans2(2 * N, std::vector<int>(2 * N, 0)); for (int i = 0; i < 2 * N; i++) { for (int j = 0; j < 2 * N; j++) { int index = i + j; int k = j; if (index >= 2 * N) k = 2 * N - 1 - i; ans2[i][j] = ans[index][k]; } } return ans2; }
#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...