Submission #1249763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249763		QwertyPi	World Map (IOI25_worldmap)	C++20	12 / 100	10 ms	1348 KiB

worldmap

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

using namespace std;

const int N_MAX = 40 + 11;
vector<int> G[N_MAX], adj[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);
            }
        }
    }
    return ans;
}

bool vis[N_MAX];
int sz[N_MAX], dep[N_MAX];

void dfs0(int v, int pa = -1) {
    vis[v] = true; sz[v] = 1;
    for (int u : G[v]) {
        if (vis[u]) continue;
        dep[u] = dep[v] + 1;
        dfs0(u, v);
        sz[v] += sz[u];
    }
}

vector<vector<int>> ans;
void paint(int x, int y, int c) {
    if (x < 0 || x >= ans.size() || y < 0 || y >= ans[0].size()) return;
    ans[x][y] = c;
}

void paint2(int x, int y, int c1, int c2) {
    paint(x, y, c1);
    for (auto [dx, dy] : vector<pair<int, int>>{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
        paint(x + dx, y + dy, c2);
    }
}

int _N;
void dfs(int v, int pa, int x = 0, int y = 0, bool is_last = true) {
    // cout << "DFS " << v << ' ' << pa << ' ' << x << ' ' << y << endl;
    vis[v] = true;
    for (int i = 0; i < (is_last ? _N - y / 2: sz[v] - 1); i++) {
        // paint(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v);
        paint2(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v, v);
    }
    int lst = G[v].empty() ? -1 : G[v].back();
    for (int u : G[v]) {
        if (vis[u]) continue;
        dfs(u, v, x + 2, y, u == lst);
        y += sz[u] * 2;

        if (u != lst) {
            for (int i = x + 2; i < _N * 2; i++) {
                paint(i, y + (x % 4 / 2) - 2, v);
            }
        }
    }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    _N = N;
    for (int i = 1; i <= N; i++) {
        G[i].clear(); adj[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]);
    }
    // for (int i = 1; i <= N; i++) {
    //     cout << "G[" << i << "] => "; for (auto x : G[i]) cout << x << ' '; cout << endl;
    // }
    dfs0(1);
    for (int i = 0; i < M; i++) {
        if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
        adj[A[i]].push_back(B[i]);
    }
    
    ans = vector(N * 2, vector<int> (N * 2));
    fill(vis, vis + N + 1, false);
    dfs(1, -1);
    return regulate(ans);
}

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