Submission #1251449

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

worldmap

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    vector<vector<pair<int, int>>> adj(N+1);
    for (int i = 0; i < M; i++) {
        adj[A[i]].emplace_back(B[i], i);
        adj[B[i]].emplace_back(A[i], i);
    }

    vector<int> rizzler, loc(N+1, -1), dep(N+1);
    vector<bool> vis(N+1);
    vector<set<int>> back(N+1);
    auto dfs = [&](auto &&dfs, int u, int p) -> void {
        rizzler.push_back(u);
        loc[u] = rizzler.size();
        rizzler.push_back(u);
        rizzler.push_back(u);

        for (auto &[v, id] : adj[u]) {
            if (v == p) continue;
            if (vis[v]) {
                if (dep[u] > dep[v]) back[u].insert(v);
            } else {
                vis[v] = true;
                dep[v] = dep[u] + 1;
                dfs(dfs, v, u);
                rizzler.push_back(u);
            }
        }
    };

    vis[1] = true;
    dfs(dfs, 1, 0);

    cerr << N sp rizzler.size() << endl;
    for (auto &x : rizzler) cerr << x << " ";
    cerr << endl;

    int K = rizzler.size();
    assert(K == 4*N-1);
    vector<vector<int>> ans(2*N, vector<int>(2*N));
    for (int i = 0; i < 2*N; i++) {
        for (int j = 0; j < 2*N; j++) {
            ans[i][j] = rizzler[i+j];
        }
    }

    for (int u = 1; u <= N; u++) {
        // cerr << u sp loc[u] << endl;
        int j = loc[u], k = (j >= 2*N ? j-2*N+1 : 0);
        for (auto &v : back[u]) {
            if (0 <= k and k < 2*N and 0 <= j-k and j-k < 2*N)
                ans[k][j-k] = v;
            k++;
        }
    }

    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