Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_6 /examples /gpt5.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
6.72 kB
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// Handle trivial case
if (N == 1) {
return vector<vector<int>>(1, vector<int>(1, 1));
}
// Build adjacency list
struct Edge { int u, v; };
vector<Edge> edges(M);
for (int i = 0; i < M; ++i) {
edges[i] = {A[i], B[i]};
}
vector<vector<pair<int,int>>> adj(N+1);
for (int i = 0; i < M; ++i) {
int u = edges[i].u, v = edges[i].v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
// If graph might be disconnected or have isolated nodes, note:
// For this construction, we assume there exists a valid map (connected or special case N=1).
// We construct a long walk W over the graph edges (possibly repeating edges) to use diagonal fill.
// Generate trails covering all edges once using greedy walks
vector<char> used(M, 0);
vector<vector<int>> trails; // each as a sequence of vertices
// A helper to find a vertex with unused edges
auto hasUnusedEdgeAt = [&](int v)->bool{
for (auto &p : adj[v]) if (!used[p.second]) return true;
return false;
};
// Make a list of all vertices with degree > 0
vector<int> verticesWithDeg;
for (int v = 1; v <= N; ++v) {
if (!adj[v].empty()) verticesWithDeg.push_back(v);
}
if (verticesWithDeg.empty()) {
// No edges but N>1 -> no valid map under constraints; return simple 1xN line with same color to satisfy existence only when possible
// However, problem guarantees existence. We'll just place a 1x1 map per safest approach for N=1 already handled.
// Fallback: create a simple 2x2 using first color.
int K = max(1, min(240, N));
vector<vector<int>> C(K, vector<int>(K, 1));
return C;
}
// Greedy trail decomposition
while (true) {
int start = -1;
for (int v = 1; v <= N; ++v) {
if (hasUnusedEdgeAt(v)) { start = v; break; }
}
if (start == -1) break;
vector<int> path;
int cur = start;
path.push_back(cur);
while (true) {
int picked = -1;
int nxt = -1;
for (auto &p : adj[cur]) {
int nb = p.first, eid = p.second;
if (!used[eid]) { picked = eid; nxt = nb; break; }
}
if (picked == -1) break;
used[picked] = 1;
cur = nxt;
path.push_back(cur);
}
trails.push_back(path);
}
// Build connectivity graph for BFS paths
vector<vector<int>> simpleAdj(N+1);
for (int i = 0; i < M; ++i) {
int u = edges[i].u, v = edges[i].v;
simpleAdj[u].push_back(v);
simpleAdj[v].push_back(u);
}
auto bfs_path = [&](int s, int t)->vector<int> {
vector<int> prev(N+1, -1);
queue<int>q;
q.push(s);
prev[s] = s;
while (!q.empty()) {
int x = q.front(); q.pop();
if (x == t) break;
for (int y : simpleAdj[x]) {
if (prev[y] == -1) {
prev[y] = x;
q.push(y);
}
}
}
vector<int> path;
if (prev[t] == -1) {
// not connected; shouldn't happen if input guarantees existence
// Return direct s->t (invalid if no edge); but keep s only to avoid breaking
path.push_back(s);
return path;
}
int cur = t;
while (cur != s) {
path.push_back(cur);
cur = prev[cur];
}
path.push_back(s);
reverse(path.begin(), path.end());
return path; // includes both s and t
};
// Combine trails into a single long walk W
vector<int> W;
if (!trails.empty()) {
W = trails[0]; // first trail
for (size_t i = 1; i < trails.size(); ++i) {
int endW = W.back();
int startT = trails[i].front();
vector<int> bridge = bfs_path(endW, startT);
// append bridge excluding the first node (already at end of W)
for (size_t k = 1; k < bridge.size(); ++k) W.push_back(bridge[k]);
// append trail i (all vertices)
for (size_t k = 1; k < trails[i].size(); ++k) W.push_back(trails[i][k]);
}
}
// Ensure all vertices with degree>0 appear in W; if not, append them via BFS from last
vector<char> seenV(N+1, 0);
for (int x : W) if (x>=1 && x<=N) seenV[x] = 1;
int lastV = W.empty() ? verticesWithDeg[0] : W.back();
for (int v = 1; v <= N; ++v) {
if (!adj[v].empty() && !seenV[v]) {
vector<int> bridge = bfs_path(lastV, v);
for (size_t k = 1; k < bridge.size(); ++k) W.push_back(bridge[k]);
lastV = v;
seenV[v] = 1;
}
}
// If W is still empty (no edges), fallback handled earlier; but just in case
if (W.empty()) {
int K = min(240, max(1, N));
vector<vector<int>> C(K, vector<int>(K, 1));
return C;
}
// Determine K
// We can realize at most 2*K - 2 distinct consecutive pairs (indices), so we need length of W <= 2*K - 1
int maxK = 240;
int L = (int)W.size();
int K = min(maxK, max(N, (L + 1) / 2));
int needLen = 2 * K - 1;
if ((int)W.size() < needLen) {
// pad with last vertex
int padVal = W.back();
while ((int)W.size() < needLen) W.push_back(padVal);
} else if ((int)W.size() > needLen) {
// truncate if too long
W.resize(needLen);
}
// Build grid with diagonal fill: C[i][j] = W[i+j]
vector<vector<int>> C(K, vector<int>(K, 1));
for (int i = 0; i < K; ++i) {
for (int j = 0; j < K; ++j) {
int idx = i + j;
if (idx >= 0 && idx < (int)W.size()) C[i][j] = W[idx];
else C[i][j] = W.back();
}
}
return C;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; ++i) cin >> A[i] >> B[i];
auto C = create_map(N, M, A, B);
int P = (int)C.size();
cout << P << "\n";
for (int i = 0; i < P; ++i) {
cout << (int)C[i].size() << (i+1==P?'\n':' ');
}
cout << "\n";
for (int i = 0; i < P; ++i) {
for (int j = 0; j < (int)C[i].size(); ++j) {
if (j) cout << ' ';
cout << C[i][j];
}
cout << "\n";
}
}
return 0;
}