Submission #1307987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307987		fafnir	World Map (IOI25_worldmap)	C++20	12 / 100	17 ms	2876 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> 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]) {
            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;

    for (int r = row; r < row + 3; ++r) {
        for (int i = left; i <= right; ++i) {
            ma[r][i] = u;
        }
    }

    for (int r = row+3; r < MSIZE; ++r) {
        ma[r][left] = u;
        ma[r][right] = u;
    }

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

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

        if (visited[v]) {continue;}

        dfs1(v, lbound, lbound+w[v]-1, row+3, ma);
        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;
    }
    

    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(3*n, vector<int>(3*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 < 3*N; ++y) {
        for (int x = 0; x < 3*N; ++x) {
            rmap[y][x] = max(1, rmap[y][x]);
        }
    }

    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