Submission #1251031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251031		countless	World Map (IOI25_worldmap)	C++20	86 / 100	46 ms	5564 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> sigma;
    vector<bool> vis(N+1);
    auto dfs = [&](auto &&dfs, int u) -> void {
        sigma.push_back(u);
        for (auto &[v, id] : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            dfs(dfs, v);
            sigma.push_back(u);
        }
    };

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

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

    vector<int> rizzler, loc(N+1, 0);
    vector<bool> vis2(N+1);
    for (auto &x : sigma) {
        if (vis2[x]) rizzler.emplace_back(x);
        else {
            vis2[x] = true;
            rizzler.emplace_back(x);
            loc[x] = rizzler.size();
            rizzler.emplace_back(x);
            rizzler.emplace_back(x);
        }
    }

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

    rizzler.pop_back();
    int K = rizzler.size();
    vector<vector<int>> ans(3*N, vector<int>(3*N, 1));
    // cerr << "K" sp K << endl;
    for (int i = 0; i < K; i++) {
        // at +N
        for (int j = 0; j < i+N; j++) {
            if (j < 0 or j >= 3*N or N+i-j-1 < 0 or N+i-j-1 >= 3*N) continue;
            ans[j][N+i-j-1] = rizzler[i];
        }
    }

    vector<vector<bool>> vis3(N+1, vector<bool>(N+1));
    for (int i = 1; i <= N; i++) {
        int j = loc[i], k = (j+N > 3*N ? j-2*N : 0);
        // cerr << j << endl;
        for (auto &[v, id] : adj[i]) {
            if (vis3[i][v]) continue;
            vis3[i][v] = true;
            // cerr << "put" sp v sp "at" sp k sp N+j-k-1 << endl;
            if (0 <= k and k < 3*N and 0 <= N+j-k-1 and N+j-k-1 < 3*N)
                ans[k][N+j-k-1] = 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: 42 / 56