Submission #1253675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253675		TrendBattles	World Map (IOI25_worldmap)	C++17	72 / 100	71 ms	9288 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

using namespace std;


vector <vector <int>> create_map(int N, int M, vector <int> A, vector <int> B) {
    if (M == 0) {
        return {{1}};
    }
    
    vector <int> temp_id(N + 1);
    iota(temp_id.begin(), temp_id.end(), 0);
    
    vector <vector <int>> connected(N + 1, vector <int> (N + 1));
    vector <vector <int>> dsu_graph(N + 1);
    for (int i = 0; i < M; ++i) {
        connected[A[i]][B[i]] = connected[B[i]][A[i]] = true;

        int u = temp_id[A[i]], v = temp_id[B[i]];
        if (u == v) continue;
        
        dsu_graph[A[i]].push_back(B[i]);
        dsu_graph[B[i]].push_back(A[i]);
        for (int p = 1; p <= N; ++p) {
            if (temp_id[p] == v) temp_id[p] = u;
        }
    }
    

    vector <vector <int>> finale;
    auto DFS = [&] (auto DFS, int u) -> void {
        finale.emplace_back();
        for (int i = 1; i <= N; ++i) {
            if (connected[u][i] == false) continue;

            finale.back().push_back(u);
            finale.back().push_back(i);
        }
        finale.emplace_back();
        finale.back().push_back(u);
        
        for (int v : dsu_graph[u]) {
            dsu_graph[v].erase(find(dsu_graph[v].begin(), dsu_graph[v].end(), u));

            finale.emplace_back();
            finale.back().push_back(v);

            DFS(DFS, v);

            finale.emplace_back();
            finale.back().push_back(u);
        }
    };  
    DFS(DFS, 1);

    int K = (int) finale.size();
    for (vector <int>& F : finale) {
        while ((int) F.size() < K) F.push_back(F[0]);
    }
    return finale;
}

• 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