Submission #682898

#	Time	Username	Problem	Language	Result	Execution time	Memory
682898		peijar	Airline Route Map (JOI18_airline)	C++17	0 / 100	1554 ms	72344 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#include <cassert>
#include <cstdio>

const int MAXBIT = 10;

void Alice(int nbSommet, int nbAretes, int A[], int B[]) {
  int sommetInit = nbSommet;
  vector<int> rootBit;
  for (int p = 0; p < MAXBIT; ++p)
    rootBit.push_back(nbSommet++);

  vector<pair<int, int>> aretes;
  for (int i = 0; i < nbAretes; ++i)
    aretes.emplace_back(A[i], B[i]);

  int root1 = nbSommet++;
  int root2 = nbSommet++;

  for (int i = 0; i < nbSommet; ++i)
    if (i != root2 and i != root1)
      aretes.emplace_back(root1, i);
  for (int i : rootBit)
    aretes.emplace_back(root2, i);

  for (int i = 0; i < MAXBIT - 1; ++i)
    aretes.emplace_back(rootBit[i], rootBit[i + 1]);
  aretes.emplace_back(rootBit[0], rootBit[2]);

  for (int u = 0; u < sommetInit; ++u)
    for (int p = 0; p < MAXBIT; ++p)
      if ((1 << p) & u)
        aretes.emplace_back(rootBit[p], u);

  InitG(nbSommet, aretes.size());
  for (int i = 0; i < (int)aretes.size(); ++i) {
    auto [u, v] = aretes[i];
    MakeG(i, u, v);
  }
}

Bob

#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

#include "Boblib.h"
#include <cassert>
#include <cstdio>

const int MAXBIT = 10;

void Bob(int nbSommet, int nbAretes, int C[], int D[]) {
  vector<set<int>> adj(nbSommet);
  for (int i = 0; i < nbAretes; ++i) {
    adj[C[i]].insert(D[i]);
    adj[D[i]].insert(C[i]);
  }
  for (int i = 0; i < nbSommet; ++i)
    dbg(i, adj[i]);

  int root = -1;
  for (int u = 0; u < nbSommet; ++u)
    if ((int)adj[u].size() == nbSommet - 2)
      root = u;

  assert(root != -1);
  int root2 = 0;
  while (root == root2 or adj[root].count(root2))
    ++root2;
  assert(root2 < nbSommet);
  dbg(root, root2);

  vector<int> rootBit;
  for (int u = 0; u < nbSommet; ++u)
    if (adj[root2].count(u))
      rootBit.push_back(u);

  assert((int)rootBit.size() == MAXBIT);

  do {
    bool ok = adj[rootBit[0]].count(rootBit[2]);
    for (int i = 0; i < MAXBIT - 1 and ok; ++i)
      ok &= adj[rootBit[i]].count(rootBit[i + 1]);
    if (ok)
      break;
  } while (next_permutation(rootBit.begin(), rootBit.end()));

  dbg(rootBit);
  vector<bool> real(nbSommet, true);
  real[root] = real[root2] = false;
  for (int u : rootBit)
    real[u] = false;

  vector<int> realName(nbSommet);
  for (int u = 0; u < nbSommet; ++u)
    if (real[u])
      for (int p = 0; p < MAXBIT; ++p)
        if (adj[rootBit[p]].count(u))
          realName[u] |= 1 << p;

  vector<pair<int, int>> edges;
  for (int u = 0; u < nbSommet; ++u)
    if (real[u])
      for (int v : adj[u])
        if (real[v] and realName[u] < realName[v]) {
          edges.emplace_back(realName[u], realName[v]);
          dbg(realName[u], realName[v]);
        }

  InitMap(nbSommet - 2 - MAXBIT, edges.size());
  for (auto [u, v] : edges)
    MakeMap(u, v);
}

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