Submission #1250595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250595		countless	World Map (IOI25_worldmap)	C++20	29 / 100	23 ms	3140 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) {
    // subtask 1
    // vector<vector<int>> ans(N, vector<int>(N));
    // deque<int> o(N);
    // for (int i = 0; i < N; i++) {
    //     fill(o.begin(), o.end(), i+1);
    //     ans[i] = vector<int>(o.begin(), o.end());
    // }

    // subtask 3
    // rainbow?
    // vector<vector<int>> ans(N, vector<int>(N));
    // deque<int> o(N);
    // iota(o.begin(), o.end(), 1);
    // for (int i = 0; i < N; i++) {
    //     ans[i] = vector<int>(o.begin(), o.end());
    //     for (int j = 0; j < i+1; j++) {
    //         o.push_front(o.back());
    //         o.pop_back();
    //     }
    // }
    
    // subtask 2/4
    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[id]) continue;
            vis[id] = true;
            dfs(dfs, v);
            sigma.push_back(u);
        }
    };

    dfs(dfs, 1);

    int K = sigma.size();
    assert(K <= 250);
    vector<vector<int>> ans(K, vector<int>(K));
    for (int i = 0; i < K; i++) ans[i] = sigma;


    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 14 / 14
• Subtask 6: 0 / 56