Submission #1250993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250993		countless	World Map (IOI25_worldmap)	C++20	72 / 100	74 ms	9544 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(M);
    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);
        }
    };

    dfs(dfs, 1);

    cerr << N sp sigma.size() << 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;

    rizzler.pop_back();
    int K = rizzler.size();
    vector<vector<int>> ans(K, vector<int>(K));
    for (int i = 0; i < K; i++) {
        ans[i] = rizzler;
    }

    vector<vector<bool>> vis3(N+1, vector<bool>(N+1));
    for (int i = 1; i <= N; i++) {
        int j = loc[i], k = 0;
        for (auto &[v, id] : adj[i]) {
            if (vis3[i][v]) continue;
            vis3[i][v] = true;
            ans[k][j] = v;
            k += 2;
        }
    }

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