Submission #1249715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249715		QwertyPi	World Map (IOI25_worldmap)	C++20	86 / 100	42 ms	5488 KiB

worldmap

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

using namespace std;

const int N_MAX = 40 + 11;
vector<int> G[N_MAX];

vector<vector<int>> regulate(vector<vector<int>> board) {
    int n = board.size(), m = board[0].size();
    int K = max(n, m);
    vector ans = vector(K, vector<int>(K));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            if (!ans[i][j]) {
                if (j > 0 && ans[i][j - 1]) ans[i][j] = ans[i][j - 1];
                else if (i > 0 && ans[i - 1][j]) ans[i][j] = ans[i - 1][j];
                else assert(false);
            }
        }
    }
    // for (int i = 0; i < K; i++) {
    //     for (int j = 0; j < K; j++) {
    //         cout << ans[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    return ans;
}

bool vis[N_MAX];
vector<pair<int, bool>> st;
void dfs(int v, int pa = -1) {
    vis[v] = true;
    for (int u : G[v]) {
        if (vis[u]) continue;
        st.push_back({u, true});
        dfs(u, v);
        st.push_back({v, false});
    }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    for (int i = 1; i <= N; i++) {
        G[i].clear();
    }
    fill(vis, vis + N + 1, false);
    for (int i = 0; i < M; i++) {
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    st = vector<pair<int, bool>>{{1, true}}; dfs(1);

    vector ans = vector(N * 4, vector<int> (N * 2));
    int x = 0;
    bool odd = true;
    for (auto [v, fi] : st) {
        if (fi) {
            for (int j = -1; j <= 1; j++) {
                for (int k = 0; k < N * 2; k++) {
                    if (x + j >= 0 && ((j + k + 2) % 2 == !odd || j == 0)) ans[x + j][k] = v;
                }
            }
            for (int j = 0; j < G[v].size(); j++) {
                ans[x][j * 2 + odd] = G[v][j];
            }
            x += 2;
            odd = !odd;
        } else {
            for (int k = 0; k < N * 2; k++) {
                ans[x + (k + odd) % 2 - 1][k] = v;
            }
            x++;
        }
    }
    ans.resize(x - 1);
    return regulate(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