結果

問題 No.382 シャイな人たち (2)
ユーザー Min_25Min_25
提出日時 2016-06-19 06:08:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,177 ms / 8,000 ms
コード長 5,273 bytes
コンパイル時間 771 ms
コンパイル使用メモリ 79,956 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 05:18:18
合計ジャッジ時間 22,610 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,177 ms
5,248 KB
testcase_01 AC 1,177 ms
5,248 KB
testcase_02 AC 1,020 ms
5,248 KB
testcase_03 AC 963 ms
5,248 KB
testcase_04 AC 957 ms
5,248 KB
testcase_05 AC 1,036 ms
5,248 KB
testcase_06 AC 839 ms
5,248 KB
testcase_07 AC 1,084 ms
5,248 KB
testcase_08 AC 843 ms
5,248 KB
testcase_09 AC 867 ms
5,248 KB
testcase_10 AC 939 ms
5,248 KB
testcase_11 AC 909 ms
5,248 KB
testcase_12 AC 927 ms
5,248 KB
testcase_13 AC 949 ms
5,248 KB
testcase_14 AC 1,041 ms
5,248 KB
testcase_15 AC 1,069 ms
5,248 KB
testcase_16 AC 960 ms
5,248 KB
testcase_17 AC 845 ms
5,248 KB
testcase_18 AC 1,082 ms
5,248 KB
testcase_19 AC 993 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <tuple>

#define _fetch(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

using u128 = __uint128_t;

const u32 N_MAX = 120;

int degs[N_MAX + 1];
u128 V_deg[N_MAX + 2];
u128 edges[N_MAX + 1];

inline int ctz(u128 n) {
  if (u64(n)) return __builtin_ctzll(u64(n));
  else return 64 + __builtin_ctzll(u64(n >> 64));
}

inline int pop_count(u128 n) {
  if (u64(n)) return __builtin_popcountll(u64(n)) + __builtin_popcountll(u64(n >> 64));
  else return __builtin_popcountll(u64(n >> 64));
}

inline void delete_v(u128 G, int v) {
  auto Nv = edges[v] & G;
  while (Nv) {
    auto fy = Nv & -Nv;
    int y = ctz(fy);
    V_deg[degs[y]--] ^= fy;
    V_deg[degs[y]] ^= fy;
    Nv ^= fy;
  }
}

inline void insert_v(u128 G, int v) {
  auto Nv = edges[v] & G;
  while (Nv) {
    auto fy = Nv & -Nv;
    int y = ctz(fy);
    V_deg[degs[y]++] ^= fy;
    V_deg[degs[y]] ^= fy;
    Nv ^= fy;
  }
}

inline void delete_V(u128 G, u128 V) {
  while (V) {
    auto fv = V & -V;
    int v = ctz(fv);
    delete_v(G, v);
    V ^= fv;
  }
}

inline void insert_V(u128 G, u128 V) {
  while (V) {
    auto fv = V & -V;
    int v = ctz(fv);
    insert_v(G, v);
    V ^= fv;
  }
}

// P(v, is_clique)
using P = pair<int, bool>;
inline P max_deg_vertex(u128 G, u128 S, int beg) {
  for (int deg = beg; ; ++deg) {
    u128 Vd = V_deg[deg] & G;
    if ((S |= Vd) != G) continue;
    auto fv = Vd & -Vd;
    int v = ctz(fv);
    return P(v, (Vd == G) && (pop_count(G) == deg + 1));
  }
}

int vertices[N_MAX];

// Naive: O(3^(n/3)) ~= O(1.4422^n)
int mis1(u128 G) {
  if (G == 0) return 0;
  for (int deg = 0; ; ++deg) if (V_deg[deg] & G) {
    int i_max = 0;
    auto fv = V_deg[deg] & G; fv &= -fv;
    int v = ctz(fv);
    auto Nv = (fv ^ edges[v]) & G;
    while (Nv) {
      auto fy = Nv & -Nv;
      int y = ctz(fy);
      auto Ny = edges[y] & G;
      delete_v(G, y);
      i_max = max(i_max, mis1(G ^ (Ny | fy)));
      insert_v(G, y);
      Nv ^= fy;
    }
    return 1 + i_max;
  }
}

// O(1.2905^n)
int mis3(u128 G, int idx=0) {
  if (G == 0) return 0;

  // d(v) <= 1
  const u128 V01 = (V_deg[0] | V_deg[1]) & G;
  if (V01) {
    auto fv = V01 & -V01;
    int v = ctz(fv);
    auto Nv = edges[v] & G;
    delete_V(G, Nv); vertices[idx] = v;
    int ret = 1 + mis3(G ^ (Nv | fv), idx + 1);
    insert_V(G, Nv);
    return ret;
  }

  // d(v) >= 3
  const u128 V2 = V_deg[2] & G;
  if (V2 != G) {
    auto p = max_deg_vertex(G, V2, 3);
    auto v = p.first;
    auto fv = u128(1) << v;
    if (p.second == true) {
      vertices[idx++] = v;
      return 1;
    } else {
      int vertices_back[N_MAX];

      // G \ v
      delete_v(G, v);
      int ret = mis3(G ^ fv, idx); copy(vertices + idx, vertices + idx + ret, vertices_back);
      insert_v(G, v);

      // G \ N(v)
      auto Nv = edges[v] & G;
      delete_V(G, Nv); vertices[idx] = v;
      int ret2 = 1 + mis3(G ^ (Nv | fv), idx + 1);
      insert_V(G, Nv);

      if (ret > ret2) {
        copy(vertices_back, vertices_back + ret, vertices + idx);
      } else {
        ret = ret2;
      }
      return ret;
    }
  }

  // Delta(G) = delta(G) = 2
  int ret = 0;
  while (G) {
    auto fv = G & -G;
    int cycle_len = 0;
    for (; fv; ++cycle_len) {
      int v = ctz(fv);
      G ^= fv;
      fv = edges[v] & G; fv &= -fv;
      if (cycle_len & 1) vertices[idx++] = v;
    }
    ret += cycle_len / 2;
  }
  return ret;
}

struct Rand {
  Rand(u32 seed) : x(seed) {}
  u32 next() { return x = u64(x) * 12345 % 1000003; }
  u32 x;
};

int gene_graph(int S) {
  auto gene = Rand(S);
  int N = gene.next() % N_MAX + 2;
  int P = gene.next();
  // fprintf(stderr, "N: %u, P: %u\n", N, P);
  rep(i, N) {
    degs[i] = V_deg[i] = edges[i] = 0;
  }
  rep(i, N) rep(j, i + 1, N) {
    int X = gene.next();
    if (X >= P) {
      edges[i] |= u128(1) << j; degs[i]++;
      edges[j] |= u128(1) << i; degs[j]++;
      // fprintf(stderr, "S: %u, E: %u <-> %u (%u)\n", S, i, j, X);
    }
  }
  rep(i, N) V_deg[degs[i]] |= u128(1) << i;
  return N;
}

void solve() {
  int S;
  // clock_t worst = 0;
  while (~scanf("%d", &S)) {
    int N = gene_graph(S);
    auto G = (u128(1) << N) - 1;
    // clock_t beg = clock();
    int len = mis3(G);
    // clock_t end = clock();
    // if (end - beg > worst) {
    //   worst = end - beg;
    //   printf("%u: %d %.3f\n", S, pop_count(G), double(worst) / CLOCKS_PER_SEC);
    // }
    if (len == pop_count(G)) {
      puts("-1");
    } else {
      printf("%u\n", len + 1);
      printf("%u", vertices[0] + 1);
      rep(i, 1, len) printf(" %u", vertices[i] + 1);
      puts("");
    }
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0