Submission #925219

#	Time	Username	Problem	Language	Result	Execution time	Memory
925219		huutuan	Airline Route Map (JOI18_airline)	C++14	0 / 100	438 ms	37852 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>> ans;
   for (int i=0; i<m; ++i){
      ans.emplace_back(a[i], b[i]);
   }
   for (int i=0; i<n+10; ++i) if (i!=n) 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 (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);
}

Bob

#include "Boblib.h"

#include <bits/stdc++.h>

using namespace std;

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

void Bob(int v, int u, int c[], int d[]){
   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;
   vector<int> idx;
   for (int i=0; i<v; ++i) if (i!=id[10] && !adj[id[10]][i]) idx.push_back(i);
   if (deg[idx[0]]<deg[idx[1]]) swap(idx[0], idx[1]);
   id[11]=idx[0];
   id[0]=idx[1];
   isfake[id[11]]=1;
   isfake[id[0]]=1;
   vector<int> bit{id[0]};
   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);
   }
   vector<int> realbit;
   realbit.push_back(id[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(code[c[i]], code[d[i]]);
      }
   }
   InitMap(v-12, ans.size());
   for (auto &i:ans) MakeMap(i.first, i.second);
}

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