Submission #1253673

#TimeUsernameProblemLanguageResultExecution timeMemory
1253673TrendBattlesWorld Map (IOI25_worldmap)C++17
0 / 100
54 ms7240 KiB
#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) { 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...