Submission #1249949

#TimeUsernameProblemLanguageResultExecution timeMemory
1249949ZicrusWorld Map (IOI25_worldmap)C++20
86 / 100
198 ms4468 KiB
#include <bits/stdc++.h> #include "worldmap.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define all(v) v.begin(), v.end() constexpr ll inf = 1ll << 62ll; mt19937 mt(62434); ll _ = 0; void fix_answer1(vector<vector<int>> &res) { ll k = res.size(); for (ll i = 0; i < k; i++) { for (ll j = 0; j < k; j++) { res[i][j]++; } } } pair<vector<ll>, vector<ll>> get_rows1(vector<set<ll>> &adj, ll source) { ll n = adj.size(); vector<ll> rows; vector<ll> node_row(n); ll mx_used = 0; vector<ll> check; auto dfs = [&](const auto &self, ll cur) -> bool { ll child_cnt = 0; for (auto &e : adj[cur]) { child_cnt += !node_row[e]; } if (!child_cnt) return false; mx_used = node_row[cur] = rows.size() + 1; rows.push_back(cur); rows.push_back(cur); rows.push_back(cur); vector<ll> a(0); for (auto &e : adj[cur]) a.push_back(e); shuffle(all(a), mt); for (auto &e : a) { if (node_row[e]) continue; if (self(self, e)) { check.push_back(rows.size()); rows.push_back(cur); } } return true; }; dfs(dfs, source); rows.erase(rows.begin()); while (rows.size() > mx_used) rows.pop_back(); reverse(all(check)); for (auto &i : check) { i--; if (i+1 >= rows.size()) continue; if (adj[rows[i-1]].count(rows[i+1])) { rows.erase(rows.begin() + i); for (auto &e : node_row) e -= (e > i); } } return {rows, node_row}; } vector<vector<int>> create_map(int N, int M, vector<int> u, vector<int> v) { ll n = N, m = M; if (n == 1) return {{1}}; vector<set<ll>> adj(n); for (ll i = 0; i < m; i++) { adj[u[i]-1].insert(v[i]-1); adj[v[i]-1].insert(u[i]-1); } auto [rows, node_row] = get_rows1(adj, 0); for (ll it = 0; it < 5; it++) { for (ll i = 0; i < n; i++) { auto [tmp, _tmp] = get_rows1(adj, i); if (tmp.size() < rows.size()) { rows = tmp; node_row = _tmp; } } } ll k = max({(ll)rows.size(), 2 * n - 3, 2ll}); while (rows.size() < k) rows.push_back(rows.back()); vector<vector<int>> res(k); for (ll i = 0; i < k; i++) { res[i] = vector<int>(k, rows[i]); } for (ll i = 0; i < n; i++) { if (!node_row[i]) continue; ll col = 0; for (auto &e : adj[i]) { res[node_row[i]-1][col] = e; col += 2; } } fix_answer1(res); return res; } #ifdef TEST #include "grader.cpp" #endif
#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...