Submission #1251470

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

worldmap

#ifndef rtgsp
#include "worldmap.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1602;
int n, m, cnt, diag, d[maxn], from[maxn], to[maxn], mx[maxn], best[maxn];
bool visited[maxn];
vector<int> euler, be[maxn], adj[maxn];

void dfs (int u)
{
    euler.push_back(u);
    visited[u] = true;
    for (int v : adj[u])
    {
        if (visited[v])
        {
            if (d[u] < d[v])
            {
                from[++cnt] = u;
                to[cnt] = v;
            }
        }
        else
        {
            d[v] = d[u] + 1;
            dfs(v);
            euler.push_back(u);
        }
    }
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B)
{
    n = N; m = M; cnt = 0; euler.clear();
    vector<vector<int>> mp(2*n, vector<int>(2*n, 1));
    for (int i = 1; i <= n; i++)
    {
        d[i] = 0;
        mx[i] = 0;
        visited[i] = false;
        be[i].clear();
        adj[i].clear();
    }
    for (int i = 0; i < m; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs(1);
    for (int i = 0; i < 2*n - 1; i++)
        mx[euler[i]] = max(mx[euler[i]], min(i, 2*n - 2 - i));
    for (int i = 1; i <= cnt; i++)
    {
        if (mx[from[i]] < mx[to[i]]) swap(from[i], to[i]);
        be[from[i]].push_back(to[i]);
    }
    for (int i = 0; i < 2*n - 1; i++)
    {
        if (mx[euler[i]] == min(i, 2*n - 2 - i))
            best[euler[i]] = i;
    }
    diag = 0;
    for (int i = 0; i < 2*n - 1; i++)
    {
        if (best[euler[i]] != i)
        {
            for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
                mp[j][diag - j] = euler[i];
            diag++;
        }
        else
        {
            for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
                mp[j][diag - j] = euler[i];
            diag++;
            int cur = 0;
            for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
            {
                if (cur < (int)be[euler[i]].size()) mp[j][diag - j] = be[euler[i]][cur];
                else mp[j][diag - j] = euler[i];
                cur++;
            }
            diag++;
            for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
                mp[j][diag - j] = euler[i];
            diag++;
            visited[euler[i]] = true;
        }
    }
    return mp;
}

#ifdef rtgsp
int main()
{
    freopen(task".in", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int T;
    cin >> s >> T >> T;
    while (T--)
    {
        int N, M;
        vector<int> A, B;
        A.clear(); B.clear();
        cin >> N >> M;
        for (int i = 0; i < M; i++)
        {
            int x, y;
            cin >> x >> y;
            A.push_back(x);
            B.push_back(y);
        }
        auto mp = create_map(N, M, A, B);
        for (auto i : mp)
        {
            for (auto j : i)
                cout << j << " ";
            cout << '\n';
        }
    }
}
#endif // rtgsp

• 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