Submission #1256199

#TimeUsernameProblemLanguageResultExecution timeMemory
1256199sonlh07World Map (IOI25_worldmap)C++20
44 / 100
59 ms6984 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define pp pair<int, int> #define ppp pair<pp, int> #define pp4 pair<pp, pp> #define pp3 pair<ll, pair<int, int> > #define mat vector<vector<int>> #define fi first #define se second #define mod 1000000007 #define inf 2000000001 #define esp 1e-9 #define BLOCK 333 #define BITNUM 555 #define BASE 180518 typedef long long ll; // const ll oo = (ll)1e18 + 1; using namespace std; mat concat_cols(const std::vector<mat>& childs, int parent) { int mx = 0; for (const auto& ch : childs) { mx = std::max(mx, (int)ch.size()); } mat ans; for (int i = 0; i < mx; i++) { std::vector<int> row; for (const auto& ch : childs) { int ncols = ch.empty() ? 0 : (int)ch[0].size(); row.push_back(parent); for (int j = 0; j < ncols; j++) { if (i >= (int)ch.size()) row.push_back(parent); else row.push_back(ch[i][j]); } } row.push_back(parent); ans.push_back(std::move(row)); } return ans; } mat concat_rows(const vector<mat>& childs, int parent) { int mx = 0; for (const auto &ch: childs) { mx = max(mx, (int) ch[0].size()); } // for (const auto& ch : childs) { // for (auto row: ch) { // for (int x: row) cout << x << " , "; // cout << "\n"; // } // cout << "====\n"; // } mat ans; for (const auto& ch : childs) { for (auto row: ch) { vector<int> concat_row = row; while ((int) concat_row.size() < mx) { concat_row.push_back(parent); } ans.push_back(std::move(concat_row)); } } return ans; } set<int> generated; vector<vector<int>> generate(int parent, vector<vector<int>> &adj, ll mask) { if (generated.count(parent)) { return {{parent}}; } generated.insert(parent); vector<int> childs; for (int c: adj[parent]) { // not visited if (!((mask >> c) & 1)) { childs.push_back(c); } } // no childs if (childs.size() == 0) { return {{parent}}; } vector<mat> child_maps; for (int c: childs) { auto child_map = generate(c, adj, mask | (1ll << parent)); child_maps.push_back(child_map); } sort(child_maps.begin(), child_maps.end(), [&](auto c1, auto c2){ return c1[0].size() > c2[0].size(); }); // zip them int m = (int) child_maps.size(); int w = max(1, (int) sqrt(m)); // cout << "parent: " << parent << "size = " << m << "\n"; vector<mat> rows; for (int i = 0; i < m; i += w) { int l = i; int r = min(m - 1, i + w - 1); // cout << "play[ " << l << ", " << r << " ]\n"; vector<mat> subs; for (int j = l; j <= r; j++) subs.push_back(child_maps[j]); mat center = concat_cols(subs, parent); int col = (int)center[0].size(); mat ret; vector<int> last_row(col, parent); ret.push_back(std::move(last_row)); for (auto r: center) ret.push_back(r); ret.push_back(std::move(last_row)); rows.push_back(ret); } // // temp concat all // mat ret = concat_cols(child_maps, parent); // int col = (int)ret[0].size(); // vector<int> last_row(col, parent); // ret.push_back(std::move(last_row)); // return ret; return concat_rows(rows, parent); } mat create_full_map(int N, mat &adj) { int mx = N + N; mat ret(mx, vector<int>(mx, 0)); for (int i = 0; i < N; i++) { int idx = 0; for (auto c: adj[i]) { ret[i][idx] = i; ret[i][idx + 1] = c; idx += 2; } } for (int i = 0; i < mx; i++) for (int j = 0; j < mx; j++) ret[i][j]++; return ret; } mat create_one_map(int N, vector<pp> edge) { int idx = 0; int m = edge.size(); vector<vector<int>> ret(4 * N, vector<int>(4 * N, 0)); for (int i = 0; i < N; i++) { if (idx >= m) break; int st = (i & 1) ? 0 : 2; for (int j = 0; j < N; j++) { if (idx >= m) break; ret[i][st] = edge[idx].first; ret[i][st + 1] = edge[idx].second; idx++; st += 4; } } for (int i = 0; i < 4 * N; i++) for (int j = 0; j < 4 * N; j++) ret[i][j]++; return ret; } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { generated.clear(); vector<vector<int>> adj(N, vector<int>()); for (int i = 0; i < M; i++) { int u = A[i], v = B[i]; u--; v--; adj[u].pb(v); adj[v].pb(u); } if (M == N * (N - 1) / 2) { return create_full_map(N, adj); } if (adj[0].size() == N - 1) { vector<pp> edge; for (int i = 0; i < M; i++) edge.push_back({A[i] - 1, B[i] - 1}); return create_one_map(N, edge); } auto rec_map = generate(0, adj, 1); int h = rec_map.size(); int w = rec_map[0].size(); int mx = max(h, w); vector<vector<int>> ret(mx, vector<int>(mx, 0)); for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) ret[i][j] = rec_map[i][j]; for (int i = 0; i < mx; i++) for (int j = 0; j < mx; j++) ret[i][j]++; return ret; }
#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...