Submission #829763

#	Time	Username	Problem	Language	Result	Execution time	Memory
829763		MilosMilutinovic	Airline Route Map (JOI18_airline)	C++14	100 / 100	410 ms	29432 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

void Alice(int n, int m, int a[], int b[]) {
  vector<pair<int, int>> e;
  for (int i = 0; i < m; i++) {
    e.emplace_back(a[i], b[i]);
  }
  const int L = 10;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < L; j++) {
      if ((i + 1) >> j & 1) {
        e.emplace_back(i, n + j);
      }
    }
  }
  int to_all = n + L;
  int to_bits = to_all + 1;
  for (int i = 0; i < to_all; i++) {
    e.emplace_back(i, to_all);
  }
  for (int i = n; i < n + L; i++) {
    e.emplace_back(to_bits, i);
  }

  auto Idx = [&](int x) {
    return n + x;
  };

  e.emplace_back(Idx(0), Idx(1));
  e.emplace_back(Idx(1), Idx(2));
  e.emplace_back(Idx(0), Idx(3));
  e.emplace_back(Idx(3), Idx(4));
  e.emplace_back(Idx(4), Idx(5));
  e.emplace_back(Idx(0), Idx(6));
  e.emplace_back(Idx(6), Idx(7));
  e.emplace_back(Idx(7), Idx(8));
  e.emplace_back(Idx(8), Idx(9));

  InitG(to_bits + 1, e.size());
  for (int i = 0; i < (int) e.size(); i++) {
    MakeG(i, e[i].first, e[i].second);
  }
}

/*
4 3
0 1
0 2
0 3

5 7
0 1
0 2
1 3
1 4
3 4
2 3
2 4
*/

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;

void Bob(int v, int u, int c[], int d[]) {
  const int L = 10;
  int n = v - L - 2;
  vector<vector<int>> g(v);
  for (int i = 0; i < u; i++) {
    g[c[i]].push_back(d[i]);
    g[d[i]].push_back(c[i]);
  }
  vector<int> deg(v);
  for (int i = 0; i < v; i++) {
    deg[i] = (int) g[i].size();
  }
  int to_all = (int) (max_element(deg.begin(), deg.end()) - deg.begin());
  int to_bits = -1;
  for (int i = 0; i < v; i++) {
    if (i == to_all) {
      continue;
    }
    bool ok = true;
    for (int j : g[i]) {
      if (j == to_all) {
        ok = false;
      }
    }
    if (ok) {
      assert(to_bits == -1);
      to_bits = i;
    }
  }
  vector<int> bits;
  for (int i : g[to_bits]) {
    bits.push_back(i);
  }
  vector<int> nodes;
  vector<bool> is_node(v);
  for (int i = 0; i < v; i++) {
    if (i == to_all) {
      continue;
    }
    if (i == to_bits) {
      continue;
    }
    bool is_bit = false;
    for (int j : bits) {
      if (i == j) {
        is_bit = true;
      }
    }
    if (is_bit) {
      continue;
    }
    nodes.push_back(i);
    is_node[i] = true;
  }

  vector<int> val(v, -1);
  {
    vector<bool> is_bit(v);
    for (int i : bits) {
      is_bit[i] = true;
    }
    vector<vector<int>> r(v);
    for (int i = 0; i < u; i++) {
      if (is_bit[c[i]] && is_bit[d[i]]) {
        r[c[i]].push_back(d[i]);
        r[d[i]].push_back(c[i]);
      }
    }
    int cen = -1;
    for (int i : bits) {
      if ((int) r[i].size() == 3) {
        cen = i;
      }
    }
    val[cen] = 0;
    vector<int> ch;
    function<void(int, int)> Dfs = [&](int x, int pr) {
      if (x != cen) {
        ch.push_back(x);
      }
      for (int y : r[x]) {
        if (y == pr) {
          continue;
        }
        Dfs(y, x);
        if (x == cen) {
          if ((int) ch.size() == 2) {
            val[ch[0]] = 1;
            val[ch[1]] = 2;
          } else if ((int) ch.size() == 3) {
            val[ch[0]] = 3;
            val[ch[1]] = 4;
            val[ch[2]] = 5;
          } else if ((int) ch.size() == 4) {
            val[ch[0]] = 6;
            val[ch[1]] = 7;
            val[ch[2]] = 8;
            val[ch[3]] = 9;
          }
          ch.clear();
        }
      }
    };
    Dfs(cen, cen);
  }

  vector<int> idx(v);
  for (int i : nodes) {
    for (int j : g[i]) {
      if (val[j] != -1) {
        idx[i] += (1 << val[j]);
      }
    }
  }
  vector<pair<int, int>> ans;
  for (int i = 0; i < u; i++) {
    if (is_node[c[i]] && is_node[d[i]]) {
      ans.emplace_back(idx[c[i]], idx[d[i]]);
    }
  }
  InitMap(n, (int) ans.size());
  for (int i = 0; i < (int) ans.size(); i++) {
    MakeMap(ans[i].first - 1, ans[i].second - 1);
  }
}

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