結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー yuppe19 😺
提出日時 2017-08-01 22:41:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,487 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 424 ms
コンパイル使用メモリ 55,560 KB
最終ジャッジ日時 2024-11-14 20:11:12
合計ジャッジ時間 819 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:14:3: error: ‘vector’ does not name a type
   14 |   vector<int> par;
      |   ^~~~~~
main.cpp: In constructor ‘UnionFind::UnionFind(int)’:
main.cpp:17:37: error: class ‘UnionFind’ does not have any field named ‘par’
   17 | UnionFind::UnionFind(const int n) : par(n, -1) {}
      |                                     ^~~
main.cpp: In member function ‘int UnionFind::find(int)’:
main.cpp:20:10: error: ‘par’ was not declared in this scope
   20 |   return par[x] < 0 ? x : (par[x] = find(par[x]));
      |          ^~~
main.cpp: In member function ‘void UnionFind::unite(int, int)’:
main.cpp:26:6: error: ‘par’ was not declared in this scope
   26 |   if(par[x] > par[y]) { swap(x, y); }
      |      ^~~
main.cpp:27:3: error: ‘par’ was not declared in this scope
   27 |   par[x] += par[y];
      |   ^~~
main.cpp: In member function ‘int UnionFind::size_of(int)’:
main.cpp:31:41: error: ‘par’ was not declared in this scope
   31 | int UnionFind::size_of(int x) { return -par[find(x)]; }
      |                                         ^~~
main.cpp: At global scope:
main.cpp:43:6: error: variable or field ‘shuffle’ declared void
   43 | void shuffle(vector<T> &v, int n) {
      |      ^~~~~~~
main.cpp:43:14: error: ‘vector’ was not declared in this scope
   43 | void shuffle(vector<T> &v, int n) {
      |              ^~~~~~
main.cpp:4:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    3 | #include <tuple>
  +++ |+#include <vector>
    4 | using namespace std;
main.cpp:43:22: error: expected primary-expression before ‘>’ token
   43 | void shuffle(vector<T> &v, int n) {
      |                      ^
main.cpp:43:25: error: ‘v’ was not declared in this scope
   43 | void shuffle(vector<T> &v, int n) {
      |                         ^
main.cpp:43:28: error: expected primary-expression before ‘int’
   43 | void shuffle(vector<T> &v, int n) {
      |

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
using u32 = unsigned int;

constexpr int inf = 987654321;

struct UnionFind {
  UnionFind(const int n);
  void unite(int x, int y);
  int find(int x);
  int size_of(int x); // x が含まれるグループの要素数を返す。
  vector<int> par;
};

UnionFind::UnionFind(const int n) : par(n, -1) {}

int UnionFind::find(int x) {
  return par[x] < 0 ? x : (par[x] = find(par[x]));
}

void UnionFind::unite(int x, int y) {
  x = find(x), y = find(y);
  if(x == y) { return; }
  if(par[x] > par[y]) { swap(x, y); }
  par[x] += par[y];
  par[y] = x;
}

int UnionFind::size_of(int x) { return -par[find(x)]; }

u32 uy = time(NULL);
u32 xorshift32() {
  uy ^= uy << 13;
  uy ^= uy >> 17;
  uy ^= uy << 5;
  return uy;
}

// knuth shuffle
template<class T>
void shuffle(vector<T> &v, int n) {
  if(n == 0) { return; }
  for(u32 i=n-1; i>=1; --i) {
    u32 k = xorshift32() % (i + 1);
    if(k == i) { continue; }
    swap(v[k], v[i]);
  }
}

int main(void) {
  int w, n; scanf("%d%d", &w, &n);
  vector<int> J(n);
  for(int i=0; i<n; ++i) { scanf("%d", &J[i]); }
  int m; scanf("%d", &m);
  vector<int> C(m);
  for(int i=0; i<m; ++i) { scanf("%d", &C[i]); }
  vector<vector<bool>> G(n, vector<bool>(m, true));
  for(int i=0; i<m; ++i) {
    int q; scanf("%d", &q);
    for(int j=0; j<q; ++j) {
      int x; scanf("%d", &x);
      G[--x][i] = false;
    }
  }
  vector<tuple<int, int, int>> edges;
  int V = n + m + 2;
  int s = n + m, t = s + 1;
  for(int i=0; i<n; ++i) { edges.emplace_back(s,   i, J[i]); }
  for(int i=0; i<m; ++i) { edges.emplace_back(n+i, t, C[i]); }
  for(int i=0; i<n; ++i) {
    for(int j=0; j<m; ++j) {
      if(G[i][j]) { edges.emplace_back(i, n+j, inf); }
    }
  }
  int N = edges.size();
  int mini = inf;
  for(int loop=0; loop<200000; ++loop) {
    shuffle(edges, N);
    UnionFind uf(V);
    int left = V;
    int cut = 0;
    for(auto&& tup : edges) {
      if(left <= 2) { break; }
      int u, v, _; tie(u, v, _) = tup;
      if(uf.find(u) != uf.find(v)) {
        uf.unite(u, v);
        if(uf.find(s) == uf.find(t)) { goto hell; }
        --left;
      }
    }
    for(auto&& tup : edges) {
      int u, v, c; tie(u, v, c) = tup;
      if(uf.find(u) != uf.find(v)) {
        cut += c;
        if(cut >= inf) { cut = inf; }
      }
    }
    mini = min(mini, cut);
hell:;
  }
  fprintf(stderr, "%d\n", mini);
  puts(mini >= w ? "SHIROBAKO" : "BANSAKUTSUKITA");
  return 0;
}
0