Submission #202084

#	Time	Username	Problem	Language	Result	Execution time	Memory
202084		EntityIT	Airline Route Map (JOI18_airline)	C++14	100 / 100	702 ms	31400 KiB

Alice

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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

map<int, int> id{ { 511, 1001 }, { 767, 1003 }, { 895, 1005 }, { 959, 1009 }, { 991, 1011 } };

void Alice(int N, int M, int A[], int B[]) {
  vector<pair<int, int> > edge;

  for (int i = 0; i < M; ++i) edge.emplace_back(A[i], B[i]);
  for (int i = 0; i < 10; ++i) {
    for (int u = 0; u < N; ++u) {
      if (id.count(u) ) {
        if ( (id[u] >> i) & 1) edge.emplace_back(u, N + i);
      }
      else {
        if ( (u >> i) & 1) edge.emplace_back(u, N + i);
      }
    }
    edge.emplace_back(N + i, N + 11);
    if (i + 1 < 10) edge.emplace_back(N + i, N + i + 1);
  }
  for (int u = 0; u < N; ++u) {
    edge.emplace_back(u, N + 10);
    edge.emplace_back(u, N + 11);
  }

  InitG(N + 12, sz(edge) );
  for (int i = 0; i < sz(edge); ++i) MakeG(i, edge[i].first, edge[i].second);
}

Bob

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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

map<int, int> revId{ { 1001, 511 }, { 1003, 767 }, { 1005, 895 }, { 1009, 959 }, { 1011, 991 } };

void Bob(int V, int U, int C[], int D[]){

  int N = V - 12;
  vector<vector<int> > gr(V);
  for (int i = 0; i < U; ++i) {
    gr[ C[i] ].emplace_back(D[i]);
    gr[ D[i] ].emplace_back(C[i]);
  }

  vector<int> extra(12);

  vector<int> deg(V);
  for (int i = 0; i < U; ++i) ++deg[ C[i] ], ++deg[ D[i] ];
  extra.back() = (int)(max_element(all(deg) ) - deg.begin() );

  vector<bool> vis(V); vis[extra.back()] = true;
  for (int u : gr[extra.back()]) vis[u] = true;
  extra.rbegin()[1] = (int)(find(all(vis), false) - vis.begin() );

  vis.assign(V, false); vis[extra.back()] = vis[extra.rbegin()[1] ] = true;
  for (int u : gr[ extra.rbegin()[1] ]) vis[u] = true;

  int tmp = (int)(find(all(vis), false) - vis.begin() );
  vector<int> bitNode{ tmp }; vis[tmp] = true;
  for (int u : gr[tmp]) if (!vis[u]) {
    reverse(all(bitNode) );
    for (int cur = u; cur != -1; ) {
      bitNode.emplace_back(cur); vis[cur] = true;
      int nxt = -1;
      for (int v : gr[cur]) if (!vis[v]) nxt = v;
      cur = nxt;
    }
  }
  if (N <= (1 << 9) ) {
    if (deg[ bitNode[0] ] == 2) reverse(all(bitNode) );
  }
  else {
    if (deg[ bitNode[0] ] - 2 != N / 2) reverse(all(bitNode) );
  }
  for (int i = 0; i < sz(bitNode); ++i) extra[i] = bitNode[i];

  vis.assign(V, false);
  for (int u : extra) vis[u] = true;
  vector<int> lable(V, 0);
  for (int i = 0; i < 10; ++i) {
    for (int u : gr[ extra[i] ]) if (!vis[u]) lable[u] |= 1 << i;
  }

  for (auto &i : lable) if (i >= 1000) i = revId[i];

  vector<pair<int, int> > edge;
  for (int i = 0; i < U; ++i) if (!vis[ C[i] ] && !vis[ D[i] ])
    edge.emplace_back(lable[ C[i] ], lable[ D[i] ]);

  InitMap(N, sz(edge) );
  for (auto _ : edge) {
    MakeMap(_.first, _.second);
  }
}

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