Submission #925223

#	Time	Username	Problem	Language	Result	Execution time	Memory
925223		huutuan	Airline Route Map (JOI18_airline)	C++14	100 / 100	522 ms	39872 KiB

Alice

#include "Alicelib.h"

#include <bits/stdc++.h>

using namespace std;

static const int N=2000;
static vector<int> vals;
static int rvals[N];
static int deg[N];

void Alice(int n, int m, int a[], int b[]){
   for (int i=1; i<1100; ++i) if (__builtin_popcount(i)<9){
      rvals[i]=vals.size();
      vals.push_back(i);
   }
   vector<pair<int, int>> ans;
   for (int i=0; i<m; ++i){
      ans.emplace_back(a[i], b[i]);
   }
   for (int i=0; i<n+10; ++i) ans.emplace_back(i, n+10);
   for (int i=0; i<n; ++i){
      ans.emplace_back(i, n+11);
      for (int j=0; j<10; ++j) if (vals[i]>>j&1) ans.emplace_back(i, n+j);
   }
   for (int j=1; j<10; ++j){
      ans.emplace_back(n+j-1, n+j);
   }
   InitG(n+12, ans.size());
   for (int i=0; i<(int)ans.size(); ++i) MakeG(i, ans[i].first, ans[i].second);
   for (auto &i:ans) ++deg[i.first], ++deg[i.second];
}

Bob

#include "Boblib.h"

#include <bits/stdc++.h>

using namespace std;

static const int N=2000;
static bool adj[N][N];
static int deg[N], id[20], isfake[N];
static vector<int> g[N];
static int code[N];
static int deg_bit[N];
static vector<int> vals;
static int rvals[N];

void Bob(int v, int u, int c[], int d[]){
   for (int i=1; i<1100; ++i) if (__builtin_popcount(i)<9){
      rvals[i]=vals.size();
      vals.push_back(i);
   }
   for (int i=0; i<u; ++i) ++deg[c[i]], ++deg[d[i]], adj[c[i]][d[i]]=adj[d[i]][c[i]]=1;
   id[10]=max_element(deg, deg+v)-deg;
   isfake[id[10]]=1;
   for (int i=0; i<v; ++i) if (i!=id[10] && !adj[id[10]][i]) id[11]=i;
   isfake[id[11]]=1;
   vector<int> bit{};
   for (int i=0; i<v; ++i) if (!adj[i][id[11]] && i!=id[10] && i!=id[11]){
      isfake[i]=1;
      bit.push_back(i);
   }
   for (int i=0; i<u; ++i){
      auto it1=find(bit.begin(), bit.end(), c[i]);
      auto it2=find(bit.begin(), bit.end(), d[i]);
      if (it1!=bit.end() && it2!=bit.end()) ++deg_bit[*it1], ++deg_bit[*it2];
   }
   vector<int> endpoints;
   for (int i:bit) if (deg_bit[i]==1) endpoints.push_back(i);
   if (deg[endpoints[0]]<deg[endpoints[1]]) swap(endpoints[0], endpoints[1]);
   vector<int> realbit{endpoints[0]};
   for (int i=0; i<9; ++i) for (int j:bit){
      if (find(realbit.begin(), realbit.end(), j)==realbit.end() && adj[realbit.back()][j]){
         realbit.push_back(j);
         break;
      }
   }
   for (int i=0; i<v; ++i) if (!isfake[i]){
      for (int j=0; j<10; ++j) code[i]|=(adj[i][realbit[j]])<<j;
   }
   vector<pair<int, int>> ans;
   for (int i=0; i<u; ++i){
      if (!isfake[c[i]] && !isfake[d[i]]){
         ans.emplace_back(rvals[code[c[i]]], rvals[code[d[i]]]);
      }
   }
   InitMap(v-12, ans.size());
   for (auto &i:ans) MakeMap(i.first, i.second);
}

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