Submission #1253332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253332		vuviet	World Map (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

vector<vi> create_map(int n, int m, vi a, vi b)
{
    vi c(4 * n - 1), dfs_ord;
    vector<vi> adj(n + 1);
    for (int i = 0; i < m; i++)
    {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    vector<bool> vis(n + 1, false);
    vi depth(n + 1, 0);
    vi p(n + 1, -1);
    vector<vi> ch(n + 1);
    vi tin(n + 1), tout(n + 1);
    int time = 0;
    function<void(int, int)> dfs1 = [&](int u, int par) 
    {
        vis[u] = 1, p[u] = par, tin[u] = ++time;
        for (int v : adj[u]) 
        {
            if (vis[v]) continue;
            ch[u].push_back(v);
            depth[v] = depth[u] + 1;
            dfs1(v, u);
        }
        tout[u] = time;
    };
    dfs1(1, -1);
    int id = 1;
    for (int i = 2; i <= n; i++)
        if (depth[i] > depth[id])
            id = i;
    vector<bool> bad(n + 1, false);
    while (id != 1)
    {
        bad[id] = 1;
        id = p[id];
    }
    function<void(int, int)> dfs2 = [&](int u, int par) 
    {
        dfs_ord.push_back(u);
        for (int v : ch[u]) 
            if (!bad[v]) 
            {
                dfs2(v, u);
                dfs_ord.push_back(u);
            }
        for (int v : ch[u]) 
            if (bad[v]) 
            {
                dfs2(v, u);
                dfs_ord.push_back(u);
            }
    };
    dfs2(1, -1);
    assert(dfs_ord.size() == 2 * n - 1);
    vector<vi> need(n + 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);
    }
    vector<bool> seen(n + 1, false);
    assert(need[1].size() == 0);
    vector<vi> rows;
    for (auto x : dfs_ord)
    {
        rows.push_back({x});
        if (!seen[x] && need[x].size() > 0)
        {
            rows.push_back(need[x]);
            rows.push_back({x});
            seen[x] = 1;
        }
    }
    assert(rows.size() <= 4 * n - 1);
    while (rows.size() < 4 * n - 1) 
        rows.push_back(rows.back());
    vector<vi> ans(2 * n, vi(2 * n));
    for (int i = 0; i < 4 * n - 1; i++)
    {
        int sz = min(i + 1, 4 * n - i - 1);
        assert(sz >= rows[i].size());
        assert(rows[i].size() > 0);
        while (rows[i].size() < sz) 
            rows[i].push_back(rows[i].back());
        // diag is x + y = i - 1 
        int p = 0;
        for (int x = 0; x < 2 * n; x++)
        {
            int y = i - x;
            if (0 <= y && y < 2 * n)
            {
                assert(p < rows[i].size());
                ans[x][y] = rows[i][p];
                ++p;
            }
        }
    }
    return 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: 56 / 56