Submission #44040

#	Time	Username	Problem	Language	Result	Execution time	Memory
44040		wxh010910	Airline Route Map (JOI18_airline)	C++17	0 / 100	653 ms	22632 KiB

Alice

#include "Alicelib.h"

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

void Alice(int N, int M, int A[], int B[]) {
  int V = N + 11, E = M + N + 9, cur = 0;
  for (int i = 0; i < N; ++i) {
    E += __builtin_popcount(i);
  }
  InitG(V, E);
  for (int i = 0; i < M; ++i) {
    MakeG(cur++, A[i], B[i]);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 10; ++j) {
      if (i >> j & 1) {
        MakeG(cur++, N + j, i);
      }
    }
  }
  for (int i = 1; i < 10; ++i) {
    MakeG(cur++, N + i, N + i - 1);
  }
  for (int i = 0; i < N; ++i) {
    MakeG(cur++, N + 10, i);
  }
}

Bob

#include "Boblib.h"

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

void Bob(int V, int U, int C[], int D[]) {
  static int idx[1015], deg[1015], rel[1015];
  static bool vis[1015];
  int N = V - 11, M = U - N - 9, p = -1, q = -1;
  for (int i = 0; i < N; ++i) {
    M -= __builtin_popcount(i);
  }
  InitMap(N, M);
  for (int i = 0; i < U; ++i) {
    ++deg[C[i]], vis[D[i]] = true;
  }
  for (int i = 0; i < V; ++i) {
    if (!vis[i]) {
      if (deg[i] == N) {
        p = i;
      } else {
        q = i;
      }
    }
  }
  for (int i = 0; i < V; ++i) {
    vis[i] = false, idx[i] = -1;
  }
  for (int i = 0; i < U; ++i) {
    if (C[i] == p) {
      vis[D[i]] = true;
    }
  }
  idx[q] = 9;
  for (int i = 9; i; --i) {
    for (int j = 0; j < U; ++j) {
      if (C[j] == q && !vis[D[j]]) {
        idx[q = D[j]] = i - 1;
        break;
      }
    }
  }
  for (int i = 0; i < U; ++i) {
    if (~idx[C[i]] && vis[D[i]]) {
      rel[D[i]] |= 1 << idx[C[i]];
    }
  }
  for (int i = 0; i < U; ++i) {
    if (vis[C[i]] && vis[D[i]]) {
      MakeMap(rel[C[i]], rel[D[i]]);
    }
  }
}

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