Submission #218151

#	Time	Username	Problem	Language	Result	Execution time	Memory
218151		extraterrestrial	Airline Route Map (JOI18_airline)	C++14	22 / 100	1218 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;
}

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;
  }
  vector<int> comp, cl;
  for (int i = 0; i < V; i++) {
    if (!used[i]) {
      comp = {};
      dfs(i, used, comp, g);
      vector<int> rez = get_clique(comp, ok);
      if (SZ(rez) > SZ(cl)) {
        cl = rez;
      }
    }
  }
  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]) {
        //cerr << id[v] << ' ' << id[u] << endl;
        MakeMap(id[v] - 1, id[u] - 1);
      }
    }
  }
}

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