Submission #218155

#	Time	Username	Problem	Language	Result	Execution time	Memory
218155		extraterrestrial	Airline Route Map (JOI18_airline)	C++14	37 / 100	398 ms	7416 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

void Alice(int N, int M, int A[], int B[]) {
	InitG(2 * N + 2, M + (N + 2) * (N + 1) / 2 + N * (N + 1) / 2);
  int ptr = 0;
  for (int i = 0; i < M; i++) {
    MakeG(ptr++, A[i], B[i]);
  }
  for (int i = N + 1; i <= 2 * N + 2; i++) {
    for (int j = i + 1; j <= 2 * N + 2; j++) {
      MakeG(ptr++, i - 1, j - 1);
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = N; j <= N + i; j++) {
      MakeG(ptr++, i, j);
    }
  }
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

void dfs(int v, vector<bool> &used, vector<int> &comp, vector<vector<int>> &g) {
  comp.pb(v);
  used[v] = true;
  for (auto u : g[v]) {
    if (!used[u]) {
      dfs(u, used, comp, g);
    }
  }
}

vector<int> get_clique(vector<int> &have, vector<vector<bool>> &ok) {
  vector<int> rez;
  for (int mask = 1; mask < (1 << (SZ(have))); mask++) {
    bool can = true;
    for (int i = 0; i < SZ(have); i++) {
      if ((mask >> i) & 1) {
        int v = have[i];
        for (int j = i + 1; j < SZ(have); j++) {
          if ((mask >> j) & 1) {
            int u = have[j];
            if (!ok[u][v]) {
              can = false;
            }
          }
        }
      }
    }
    if (can && __builtin_popcount(mask) > SZ(rez)) {
      rez = {};
      for (int i = 0; i < SZ(have); i++) {
        if ((mask >> i) & 1) {
          rez.pb(have[i]);
        }
      }
    }
  }  
  return rez;
}

const int N = 80;
bitset<N> a[N];
int n, need;
vector<int> ans;
 
mt19937 rnd(228);

void rec(bitset<N> can_take, bitset<N> take) {
  if (SZ(ans) == need) {
    return;
  }
  if (!can_take.count()) {
    if (take.count() > SZ(ans)) {
      ans = {};
      for (int i = 0; i < n; i++) {
        if (take[i]) {
          ans.pb(i);
        }
      }
    }
    return;
  }
  if (can_take.count() + take.count() <= SZ(ans)) {
    return;
  }
  pair<int, int> v = {-1, -1};
  for (int i = 0; i < n; i++) {
    if (can_take[i]) {
      int x = (a[i] & can_take).count();
      if (x < 2) {
        take[i] = 1;
        can_take[i] = 0;
        can_take ^= (can_take & a[i]);
        rec(can_take, take);
        return;
      }
      v = max(v, make_pair(x, i));
    }
  }
  can_take[v.S] = 0;
  take[v.S] = 1;
  rec(can_take ^ (can_take & a[v.S]), take);
  take[v.S] = 0;
  rec(can_take, take);
  take[v.S] = 0;
  can_take[v.S] = 1;
}

void Bob(int V, int U, int C[], int D[]) {
  vector<bool> used(V);
  vector<vector<int>> g(V);
  vector<vector<bool>> ok(V, vector<bool>(V));
  for (int i = 0; i < U; i++) {
    g[C[i]].pb(D[i]);
    g[D[i]].pb(C[i]);
    ok[C[i]][D[i]] = ok[D[i]][C[i]] = true;
  }
  n = V;
  need = V / 2 + 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        if (ok[i][j]) {
          a[i][j] = 0;
        }
        else {
          a[i][j] = 1;
        }
      }
    }
  }  
  bitset<N> can_take, take;
  for (int i = 0; i < n; i++) {
    can_take[i] = 1;
  }
  rec(can_take, take);
  vector<int> cl = ans;
  InitMap(V - SZ(cl), U - SZ(cl) * (SZ(cl) - 1) / 2 - (V - SZ(cl)) * (V - SZ(cl) + 1) / 2);
  vector<bool> in_clique(V);
  for (auto it : cl) {
    in_clique[it] = true;
  }
  vector<int> id(V + 1);
  for (int i = 0; i < V; i++) {
    if (!in_clique[i]) {
      int cnt = 0;
      for (auto u : g[i]) {
          if (in_clique[u]) {
          cnt++;
        }
      }
      id[i] = cnt;
    }
  }
  for (int v = 0; v < V; v++) {
    for (int u : g[v]) {
      if (id[v] && id[u] && id[v] < id[u]) {
        MakeMap(id[v] - 1, id[u] - 1);
      }
    }
  }
}

Compilation message (stderr)

Bob.cpp: In function 'void rec(std::bitset<80>, std::bitset<80>)':
Bob.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (take.count() > SZ(ans)) {
                      ^
Bob.cpp:73:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (can_take.count() + take.count() <= SZ(ans)) {
                                       ^

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