Submission #220917

#TimeUsernameProblemLanguageResultExecution timeMemory
220917rama_pangAirline Route Map (JOI18_airline)C++14
100 / 100
761 ms30920 KiB
#include "Alicelib.h" #include <bits/stdc++.h> using namespace std; namespace { struct edge_t { int u, v; edge_t() {} edge_t(int u, int v) : u(u), v(v) {} }; } void Alice(int N, int M, int A[], int B[]) { if (N == 1) return InitG(1, 0); vector<edge_t> edges; vector<int> BIT(10); for (int i = 0; i < 10; i++) BIT[i] = N + i; int ALL = N + 10, HUB = N + 11; // Original Edges for (int i = 0; i < M; i++) { edges.emplace_back(A[i], B[i]); } // Connect each vertex to its corresponding BIT vertex to be able to restore identity for (int i = 0; i < N; i++) { for (int j = 0; j < 10; j++) { if (i & (1 << j)) { edges.emplace_back(i, BIT[j]); } } } // Connect every vertex except HUB to ALL for (int i = 0; i < N + 10; i++) { edges.emplace_back(ALL, i); } // Connect every BIT vertex to HUB for (int i = 0; i < 10; i++) { edges.emplace_back(HUB, BIT[i]); } // Connect every BIT to the preceding and following bit position for (int i = 0; i < 9; i++) { edges.emplace_back(BIT[i], BIT[i + 1]); } // Initialize Transformed Graph InitG(N + 12, edges.size()); for (int i = 0; i < edges.size(); i++) { MakeG(i, edges[i].u, edges[i].v); } }
#include "Boblib.h" #include <bits/stdc++.h> using namespace std; namespace { struct edge_t { int u, v; edge_t() {} edge_t(int u, int v) : u(u), v(v) {} }; } void Bob(int V, int U, int C[], int D[]) { if (V == 1) return InitMap(1, 0); vector<edge_t> edges; int N = V - 12; vector<int> BIT(10, -1); int ALL = -1, HUB = -1; vector<int> degree(V, 0); vector<vector<bool>> adj(V, vector<bool>(V, false)); for (int i = 0; i < U; i++) { degree[C[i]]++; degree[D[i]]++; adj[C[i]][D[i]] = adj[D[i]][C[i]] = true; } // Recover ALL for (int i = 0; i < V; i++) { if (degree[i] == N + 10) { // ALL is the only vertex connected to N + 10 other vertices ALL = i; break; } } // Recover HUB for (int i = 0; i < V; i++) { if (ALL != i && !adj[ALL][i]) { // HUB is the only vertex not connected to ALL HUB = i; break; } } { // Recover BIT vector<int> BIT_shuffled; // shuffled BITs, will be recovered later vector<int> HUB_deg(V); // degree of verticeswhen only considering edges where both endpoints are adjacent to HUB vector<vector<bool>> HUB_adj(V, vector<bool>(V, false)); // adjacency matrix of vertices adjacent to hub for (int i = 0; i < V; i++) { if (HUB != i && adj[HUB][i]) { // HUB is only connected to BITs BIT_shuffled.emplace_back(i); } } // Adjacency matrix consisting of elements where both edge endpoints are connected to HUB for (auto bit : BIT_shuffled) { for (int v = 0; v < V; v++) { if (v == bit) continue; if (v == HUB) continue; if (adj[bit][v] && adj[HUB][v]) { HUB_adj[bit][v] = HUB_adj[v][bit] = true; HUB_deg[bit]++; HUB_deg[v]++; } } } // Each edge is double counted, so we divide them for (auto bit : BIT_shuffled) { HUB_deg[bit] /= 2; } // Find endpoint of BIT line int first = -1, last = -1; for (auto bit : BIT_shuffled) { if (HUB_deg[bit] == 1) { if (first == -1) { first = bit; } else { last = bit; } } } if (degree[first] < degree[last]) { swap(first, last); // BIT[0] > BIT[N - 1], we can uniquely identify the BIT sequence } // Recover Line of BITs for (int cur = first, cnt = 0, prv = -1; cnt < 10; cnt++) { BIT[cnt] = cur; for (int nxt = 0; nxt < V; nxt++) { if (cur != nxt && prv != nxt && HUB_adj[cur][nxt]) { prv = cur; cur = nxt; break; } } } } auto OriginalVertex = [&](int X) { bool res = false; res |= X == ALL; res |= X == HUB; for (int i = 0; i < 10; i++) { res |= X == BIT[i]; } return !res; }; for (int i = 0; i < U; i++) { if (OriginalVertex(C[i]) && OriginalVertex(D[i])) { edges.emplace_back(C[i], D[i]); } } auto GetIdentity = [&](int X) { int id = 0; for (int i = 0; i < 10; i++) { if (adj[X][BIT[i]]) { id |= 1 << i; } } return id; }; for (int i = 0; i < edges.size(); i++) { edges[i].u = GetIdentity(edges[i].u); edges[i].v = GetIdentity(edges[i].v); } InitMap(N, edges.size()); for (auto e : edges) { MakeMap(e.u, e.v); } }

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges.size(); i++) {
                   ~~^~~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:134:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges.size(); i++) {
                   ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...