제출 #1253401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253401		dreamnguyen	World Map (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    VuViet
 *     Created:   2025-08-05 15:58
**/

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

const int N = 50;
typedef vector<int> vi;

vi adj[N], ch[N], need[N];
int grid[2 * N][2 * N];
vector<vi> rows;

bool vis[N], back[N], seen[N];
int depth[N], p[N], tin[N], tout[N];
int dfs_ord[2 * N], len_ord, timer = 0;

void Init(int n, int m, vi a, vi b) 
{
    for (int i = 0; i <= n; ++i) 
    {
        adj[i].clear(); ch[i].clear(); need[i].clear();
        vis[i] = back[i] = seen[i] = 0;
        depth[i] = tin[i] = tout[i] = p[i] = 0;
    }
    len_ord = 0;
    rows.clear();
    for (int i = 0; i < m; ++i) 
    {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
}

void DFS(int u, int par) 
{
    vis[u] = 1, p[u] = par, tin[u] = ++timer;
    for (int v : adj[u]) 
    {
        if (vis[v]) continue;
        ch[u].push_back(v);
        depth[v] = depth[u] + 1;
        DFS(v, u);
    }
    tout[u] = timer;
}

void Mark(int n) 
{
    int id = 1;
    for (int i = 2; i <= n; ++i)
        if (depth[i] > depth[id])
            id = i;
    while (id != 1) 
    {
        back[id] = true;
        id = p[id];
    }
}

void EulerWalk(int u) 
{
    dfs_ord[len_ord++] = u;
    for (int v : ch[u])
        if (!back[v]) 
        {
            EulerWalk(v);
            dfs_ord[len_ord++] = u;
        }
    for (int v : ch[u])
        if (back[v]) 
        {
            EulerWalk(v);
            dfs_ord[len_ord++] = u;
        }
}

vector<vi> create_map(int n, int m, vi a, vi b)
{
    Init(n, m, a, b);
    DFS(1, -1);
    Mark(n);
    EulerWalk(1);
    for (int i = 0; i < m; i++) 
    {
        int u = a[i], v = b[i];
        if (u == p[v] || v == p[u]) continue;
        if (tin[v] <= tin[u] && tout[v] >= tout[u]) 
            swap(u, v);
        need[v].push_back(u);
    }    
    for (int i = 0; i < len_ord; ++i) 
    {
        int x = dfs_ord[i];
        rows.push_back({x});
        if (!seen[x] && !need[x].empty()) 
        {
            rows.push_back(need[x]);
            rows.push_back({x});
            seen[x] = true;
        }
    }
    while ((int)rows.size() < 4 * n - 1)
        rows.push_back(rows.back());
    for (int i = 0; i < 4 * n - 1; i++) 
    {
        int sz = min(i + 1, 4 * n - i - 1);
        while ((int)rows[i].size() < sz)
            rows[i].push_back(rows[i].back());
        int p = 0;
        for (int x = 0; x < 2 * n; x++) 
        {
            int y = i - x;
            if (y >= 0 && y < 2 * n)
                grid[x][y] = rows[i][p++];
        }
    }
    const int K = 7 * n;
    vector<vi> res(2 * n, vi(2 * n));
    for (int i = 0; i < 2 * n; ++i)
        for (int j = 0; j < 2 * n; ++j)
            res[i][j] = grid[i][j];
    return res;
}

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