Submission #1266140

#TimeUsernameProblemLanguageResultExecution timeMemory
1266140SharkyWorld Map (IOI25_worldmap)C++20
22 / 100
16 ms2120 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; bool vis[41], don[41]; vector<int> adj[41]; vector<pair<int, int>> ord; int deg[41], jp[41], kp[41]; set<pair<int, int>> st; void dfs(int u) { vis[u] = 1; int cnt = 0; for (auto& v : adj[u]) { if (!vis[v]) { cnt++; st.insert({u, v}); ord.push_back({u, 0}); dfs(v); ord.push_back({u, 1}); } } if (!cnt) ord.push_back({u, 0}); } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { for (int i = 0; i <= 40; i++) vis[i] = 0, adj[i].clear(), deg[i] = 0, jp[i] = 100, kp[i] = 0, don[i] = 0; ord.clear(); st.clear(); for (int i = 0; i < M; i++) { adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } dfs(1); std::vector<std::vector<int>> ans(2 * N, std::vector<int>(2 * N, 1)); int p = 0, cnt = 0, prv = 0; for (auto& [x, y] : ord) { if (!don[x]) { don[x] = 1; cnt++; for (int i = p; i < p + 3; i++) { for (int j = 0; j < 2 * N; j++) { int k = i - j; if (k >= 0 && k < 2 * N) { ans[j][k] = x; if (i == p + 1) deg[x]++, jp[x] = min(jp[x], j); kp[x] = max(kp[x], k); } } } p += 3; } else if (prv != x) { for (int j = 0; j < 2 * N; j++) { int k = p - j; if (k >= 0 && k < 2 * N) ans[j][k] = x; } p++; } prv = x; } for (int i = 0; i < M; i++) { if (st.count({A[i], B[i]}) || st.count({B[i], A[i]})) continue; if (deg[A[i]] < deg[B[i]]) swap(A[i], B[i]); deg[A[i]]--, ans[jp[A[i]]++][kp[A[i]]--] = B[i]; } 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...