Submission #1251316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251316		MojoLake	World Map (IOI25_worldmap)	C++20	86 / 100	43 ms	5448 KiB

worldmap

#include "worldmap.h"

#include <bits/stdc++.h>

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

using namespace std;

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {

    vector<vector<pair<int, int>>> g(N + 1);

    for (int i = 0; i < M; ++i) {
        g[A[i]].push_back({B[i], i});
        g[B[i]].push_back({A[i], i});
    }

    vector<int> col(N + 1);
    vector<int> handled(M);

    vector<vector<int>> ans(3 * N, vector<int> (3 * N));
    int ind = 0;
    bool flip = 0;

    auto inc = [&]() {
        ind++;
        if (ind == sz(ans)) {
            ind = 1;
            flip = 1;
        }
    };

    auto put = [&](int u) {

        if (!flip) {
            for (int y = ind, x = 0; y >= 0 && x <= ind; --y, ++x) {
                ans[y][x] = u;
            }
        } else {
            for (int y = sz(ans) - 1, x = ind; y >= ind && x < sz(ans); --y, ++x) {
                ans[y][x] = u;
            }
        }
        inc();
    };

    function<void(int, int)> dfs = [&](int u, int p) {
        col[u] = 1;
        put(u);

        // cerr << "u: " << u << "\n";

        vector<int> to_insert;
        for (auto [v, i] : g[u]) {
            if (v == p) continue;
            if (col[v]) {
                if (handled[i]) continue; // this adjacency is already accounted for
                to_insert.push_back(v);
                handled[i] = 1;
                continue;
            } else {
                dfs(v, u);
            }
            handled[i] = 1;
            put(u);
        }

        // cerr << "sz of to_insert: " << sz(to_insert) << "\n";
        // for (int x : to_insert) cerr << x << " ";
        // cerr << "\n";

        if (!to_insert.empty()) {

            while (!flip && ind + 1 < sz(to_insert)) {
                // cerr << "iterating...: " << ind + 1 << "\n";
                put(u);
            }

            if (!flip) {
                for (int y = ind, x = 0; y >= 0 && x <= ind; --y, ++x) {
                    int num = u;
                    if (!to_insert.empty()) {
                        num = to_insert.back();
                        to_insert.pop_back();
                    }
                    // cerr << "y, x: " << y << " " << x << "\n";
                    // cerr << "back: " << num << "\n";
                    ans[y][x] = num;
                }
            } else {
                for (int y = sz(ans) - 1, x = ind; y >= ind && x < sz(ans); --y, ++x) {
                    int num = u;
                    if (!to_insert.empty()) {
                        num = to_insert.back();
                        to_insert.pop_back();
                    }
                    ans[y][x] = num;
                }
            }
            
            inc();

            put(u);
        }
    };

    dfs(1, 0);
    for (auto& v : ans) {
        for (int& x : v) {
            if (x == 0) x = 1;
        }
    }
    // while (ind < sz(ans)) put(1);

    // cerr << "order:\n";
    // for (int x : order) {
    //     cerr << x << " ";
    // }
    // cerr << "\n";

    // int L = sz(order);
    // vector<vector<int>> ans(L, vector<int>(L));
    //
    // for (int i = 0; i < L; ++i) {
    //     fill(all(ans[i]), order[i]);
    // }

    return ans;
}

• 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: 42 / 56