Submission #332422

#	Time	Username	Problem	Language	Result	Execution time	Memory
332422		AlexPop28	Airline Route Map (JOI18_airline)	C++11	100 / 100	1003 ms	35708 KiB

Alice

#include "Alicelib.h"
#include <vector>

using namespace std;

void Alice(int n, int m, int A[], int B[] ){
  vector<pair<int, int>> edges;
  for (int i = 0; i < m; ++i) {
    edges.emplace_back(A[i], B[i]);
  }

  for (int bit = 0; bit < 10; ++bit) {
    for (int node = 0; node < n; ++node) {
      if (node & (1 << bit)) {
        edges.emplace_back(n + bit, node);
      }
    }
  }

  for (int node = 0; node < n; ++node) {
    edges.emplace_back(n + 10, node);
  }

  for (int bit = 1; bit < 10; ++bit) {
    edges.emplace_back(n + bit - 1, n + bit);
    edges.emplace_back(n + 11, n + bit);
  }

  InitG(n + 12, edges.size());
  for (int i = 0; i < (int)edges.size(); ++i) {
    MakeG(i, edges[i].first, edges[i].second);
  }
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

bool Try(int n, int special0,
  const vector<vector<int>> &adj, 
  const vector<pair<int, int>> &edges) {

  vector<bool> is_bit(n + 12, true);
  is_bit[special0] = false;

  for (int x : adj[special0]) {
    is_bit[x] = false;
  }

  vector<int> bits;
  for (int i = 0; i < n + 12; ++i) {
    if (is_bit[i]) bits.emplace_back(i);
  }

  assert((int)bits.size() == 11);

  int special1 = -1;
  for (int node : bits) {
    int bit_deg = 0;
    for (int x : adj[node]) {
      bit_deg += is_bit[x];
    }
    if (bit_deg == 9) {
      if (special1 != -1) return false;
      special1 = node;
    }
  }
  
  if (special1 == -1) return false;
    
  // dbg() "Found " << name(special1) endl;

  is_bit[special1] = false;

  int zero = 0;
  for (int bit : bits) {
    if (is_bit[bit]) zero ^= bit;
  }

  for (int bit : adj[special1]) {
    zero ^= bit; 
  }

  vector<int> order = {zero};
  int node = zero;
  is_bit[zero] = false;
  for (int it = 0; it < 9; ++it) {
    int next = -1;
    for (int x : adj[node]) {
      if (is_bit[x]) {
        if (next != -1) return false;
        next = x;
      }
    }

    if (next == -1) return false;
    order.emplace_back(node = next);
    is_bit[node] = false;
  }

  for (int bit : order) is_bit[bit] = true; //, dbg() bit <<  " "; dbg() endl;

  is_bit[special0] = is_bit[special1] = true;

  vector<int> label(n + 12);
  for (int bit = 0; bit < 10; ++bit) {
    int node = order[bit];
    for (int x : adj[node]) {
      if (!is_bit[x]) {
        label[x] |= 1 << bit;
      }
    }
  }

  vector<int> nodes;
  for (int i = 0; i < n + 12; ++i) {
    if (!is_bit[i]) nodes.emplace_back(label[i]);
  }
  sort(nodes.begin(), nodes.end());
  if (n != (int)nodes.size()) return false;
  for (int i = 0; i < n; ++i) if (nodes[i] != i) return false;

  vector<pair<int, int>> new_edges;
  for (auto &p : edges) {
    int x, y; tie(x, y) = p;
    if (!is_bit[x] && !is_bit[y]) {
      new_edges.emplace_back(label[x], label[y]);  
    }
  }

  sort(new_edges.begin(), new_edges.end());

//  dbg() "Edges:\n";
//  for (auto &p : new_edges) {
//    dbg() p.first << ' ' << p.second << endl;
//  }

  InitMap(n, new_edges.size());

  for (auto &p : new_edges) {
    MakeMap(p.first, p.second);
  }

  return true;
}

void Bob(int V, int U, int C[], int D[]) {
  int n = V - 12;
  vector<vector<int>> adj(V);
  vector<pair<int, int>> edges;
  for (int i = 0; i < U; ++i) {
    int x = C[i], y = D[i];
    edges.emplace_back(x, y);
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
  }

  for (int node = 0; node < V; ++node) {
    if ((int)adj[node].size() == n) {
      if (Try(n, node, adj, edges)) {
        return;
      }
    }
  }

  assert(false);
}

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63