Submission #1257121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257121		biank	세계 지도 (IOI25_worldmap)	C++20	100 / 100	26 ms	2932 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int MAX_N = 40;

vi adj[MAX_N];
bool vis[MAX_N];
set<ii> pending;
vi euler;

void dfs(int u) {
    vis[u] = true;
    euler.pb(u);
    for (int v : adj[u]) {
        if (!vis[v]) {
            dfs(v);
            pending.erase(minmax(u, v));
            euler.pb(u);
        }
    }
}

vector<vi> create_map(int N, int M, vi A, vi B) {
    forn(i, MAX_N) adj[i].clear(), vis[i] = false;
    pending.clear(), euler.clear();
    forn(i, M) {
        A[i]--, B[i]--;
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
        pending.emplace(minmax(A[i], B[i]));
    }
    dfs(0);
    forn(i, N) vis[i] = false;
    const int K = 2 * N;
    vector<vi> ret(K, vi(K));
    vector<vector<ii>> diag(2 * K);
    forn(i, K) forn(j, K) {
        diag[i + j].eb(i, j);
    }
    vector<ii> toAdd;
    int d = 0;
    for (int u : euler) {
        for (auto [i, j] : diag[d]) {
            ret[i][j] = u;
        }
        d++;
        if (!vis[u]) {
            toAdd.eb(d, u);
            d++;
            for (auto [i, j] : diag[d]) {
                ret[i][j] = u;
            }
            d++;
            vis[u] = true;
        }
    }
    while (d < 2 * K) {
        for (auto [i, j] : diag[d]) {
            ret[i][j] = euler.back();
        }
        d++;
    }
    sort(all(toAdd), [&](const auto &lhs, const auto &rhs) {
        return sz(diag[lhs.fst]) > sz(diag[rhs.fst]);
    });
    for (auto [d, u] : toAdd) {
        int idx = 0;
        for (int v : adj[u]) if (idx < sz(diag[d]) && pending.count(minmax(u, v))) {
            auto [i, j] = diag[d][idx++];
            ret[i][j] = v;
            pending.erase(minmax(u, v));
        }
        while (idx < sz(diag[d])) {
            auto [i, j] = diag[d][idx++];
            ret[i][j] = u;
        }
    }
    forn(i, K) forn(j, K) ret[i][j]++;
    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 56 / 56