Submission #1308051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308051		fafnir	World Map (IOI25_worldmap)	C++20	12 / 100	2 ms	1092 KiB

worldmap

#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;

const int NMAX = 41;
int adj[NMAX][NMAX];
int visited[NMAX];

int cnt[NMAX];  // cnt[u] := Number of child nodes in DFS-tree of node u (excluding u)
int w[NMAX];    // w[u]   := Width of node

int n;
int vtime = 1;

vector<int> children[NMAX];

vector<int> backnodes[NMAX];


int dfs0(int u, int p) {
    visited[u] = vtime++;
    int childs = 0;

    for (int v = 1; v <= n; ++v) {
        if (v == u || !adj[u][v]) {continue;}

        if (visited[v] && visited[v] < visited[u] && v != p) {
            backnodes[v].push_back(u);
        }
        
        if (!visited[v]) {
            children[u].push_back(v);
            childs += dfs0(v, u);
        }
    }

    cnt[u] = childs;
    return childs + 1;
}


void dfs1(int u, int left, int right, int row, vector<vector<int>>& ma) {
    const int MSIZE = ma.size();

    visited[u] = true;

    // Paren strip
    for (int i = left; i <= right; ++i) {
        int r = row + ((i-left)&1);
        assert(ma[r][i] == 0);
        ma[r][i] = u;
    }

    for (int r = row+1; r < MSIZE; ++r) {
        assert(max(ma[r][left], ma[r][right]) == 0);
        ma[r][left] = u;
        ma[r][right] = u;
    }

    // Add backedge nodes in strip
    int idx = left+1;
    for (auto& bnode : backnodes[u]) {
        assert(ma[row][idx] == 0);
        ma[row][idx] = bnode;
        if (row-1 >= 0) {
            assert(ma[row-1][idx] == 0);
            ma[row-1][idx] = u;
        }
        idx += 2;
    }

    while (idx <= right) {
        assert(ma[row][idx] == 0);
        ma[row][idx] = u;
        if (row-1 >= 0) {
            assert(ma[row-1][idx] == 0);
            ma[row-1][idx] = u;
        } 
        idx += 2;
    }

    int lbound = left+1;
    for (int v : children[u]) {
        // Children draws from [lbound ... lbound + w[v]-1]
        dfs1(v, lbound, lbound+w[v]-1, row+2, ma);

        // Draw separating border of parent node if more than 1 child
        // If lbound
        if (lbound+w[v] < right) {
            for (int r = row+2; r < MSIZE; ++r) {
                assert(ma[r][lbound+w[v]] == 0);
                ma[r][lbound+w[v]] = u;
            }
        }

        lbound += w[v]+1;
    }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    
    // Initialize
    vtime = 1;
    n = N;

    for (int u = 1; u <= n; ++u) {
        backnodes[u].clear();
        visited[u] = 0;
        cnt[u] = 0;
        w[u] = 0;
        children[u].clear();

        for (int v = 1; v <= n; ++v) {
            adj[u][v] = adj[v][u] = 0;
        }
    }
    

    for (int i = 0; i < M; ++i) {
        int u = A[i];
        int v = B[i];
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    dfs0(1, -1);

    vector<vector<int>> rmap(2*n, vector<int>(2*n,0));

    for (int u = 1; u <= n; ++u) {
        w[u] = 2*cnt[u] + 1;
    }

    for (int i = 1; i <= n; ++i) {visited[i] = 0;}

    dfs1(1,0,w[1]-1,0,rmap);

    // Fill every empty spot with color of root
    for (int y = 0; y < 2*N; ++y) {
        for (int x = w[1]; x < 2*N; ++x) {
            assert(rmap[y][x] == 0);
            rmap[y][x] = 1;
        }
    }

    return rmap;
}

• 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