Submission #67527

#TimeUsernameProblemLanguageResultExecution timeMemory
67527Andrei1998Airline Route Map (JOI18_airline)C++17
100 / 100
2431 ms76512 KiB
#include "Alicelib.h" #include <bits/stdc++.h> using namespace std; void Alice(int N, int M, int A[], int B[]) { // Graph const int V = N + 11; vector <pair <int, int> > edges; for (int i = 0; i < M; ++ i) edges.emplace_back(A[i], B[i]); // Encode in binary for (int i = 0; i < 10; ++ i) { for (int j = 0; j < N; ++ j) { if (j & (1 << i)) { edges.emplace_back(N + i, j); } } // Add control node edges edges.emplace_back(N + 10, N + i); } // Generate random vector mt19937 mt(123); uniform_int_distribution <int> dist(0, 1); // Add clique for (int i = 0; i < 10; ++ i) { for (int j = 0; j < i; ++ j) { const bool val = dist(mt); if (val) edges.emplace_back(N + j, N + i); } } // Send graph const int U = edges.size(); InitG(V, U); for (int i = 0; i < U; ++ i) { MakeG(i, edges[i].first, edges[i].second); } }
#include "Boblib.h" #include <bits/stdc++.h> using namespace std; void Bob(int V, int U, int C[], int D[]) { // Graph vector <vector <int> > graph(V, vector <int>()); set <pair <int, int> > graphEdges; for (int i = 0; i < U; ++ i) { graph[C[i]].push_back(D[i]); graph[D[i]].push_back(C[i]); graphEdges.insert(make_pair(C[i], D[i])); graphEdges.insert(make_pair(D[i], C[i])); } // Map const int N = V - 11; vector <pair <int, int> > mapEdges; mt19937 mt(123); uniform_int_distribution <int> dist(0, 1); int labels[10][10]; for (int i = 0; i < 10; ++ i) { for (int j = 0; j < i; ++ j) { const bool val = dist(mt); labels[i][j] = val; } } // Identify helper node int node = -1; vector <int> v; for (int i = 0; i < V; ++ i) { if (graph[i].size() == 10) { bool found = false; function <void(int)> backtr = [&](int pos) { for (int index = 0; index + 1 < pos; ++ index) if (graphEdges.count(make_pair(v[index], v[pos - 1])) != labels[pos - 1][index]) return ; if (pos == 10) { found = true; return ; } for (int index = 0; index < graph[i].size(); ++ index) { if (found) break; const int nd = graph[i][index]; swap(graph[i][index], graph[i].back()); graph[i].pop_back(); v.push_back(nd); backtr(pos + 1); if (!found) v.pop_back(); graph[i].push_back(nd); swap(graph[i][index], graph[i].back()); } }; backtr(0); if (found) { node = i; break; } } } // Find shuffle used set <int> specials = {node}; for (int i = 0; i < 10; ++ i) { const int node = v[i]; specials.insert(node); } vector <int> perm(V); for (int i = 0; i < 10; ++ i) { const int node = v[i]; for (auto it: graph[node]) { if (!specials.count(it)) { perm[it] += (1 << i); } } } // Reconstruct edges for (int i = 0; i < V; ++ i) if (!specials.count(i)) for (auto it: graph[i]) if (!specials.count(it) && i < it) mapEdges.push_back(make_pair(perm[i], perm[it])); // Send graph const int M = mapEdges.size(); InitMap(N, M); for (int i = 0; i < M; ++ i) { MakeMap(mapEdges[i].first, mapEdges[i].second); } }

Compilation message (stderr)

Bob.cpp: In lambda function:
Bob.cpp:39:75: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (graphEdges.count(make_pair(v[index], v[pos - 1])) != labels[pos - 1][index])
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Bob.cpp:47:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int index = 0; index < graph[i].size(); ++ index) {
                                     ~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...