結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー yuppe19 😺
提出日時 2017-08-01 22:41:54
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,444 ms / 2,000 ms
コード長 2,487 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,759 ms
コンパイル使用メモリ 186,564 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-03-08 16:12:59
合計ジャッジ時間 10,932 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   int w, n; scanf("%d%d", &w, &n);
      |             ~~~~~^~~~~~~~~~~~~~~~
main.cpp:55:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |   for(int i=0; i<n; ++i) { scanf("%d", &J[i]); }
      |                            ~~~~~^~~~~~~~~~~~~
main.cpp:56:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |   int m; scanf("%d", &m);
      |          ~~~~~^~~~~~~~~~
main.cpp:58:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |   for(int i=0; i<m; ++i) { scanf("%d", &C[i]); }
      |                            ~~~~~^~~~~~~~~~~~~
main.cpp:61:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
main.cpp:63:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |       int x; scanf("%d", &x);
      |              ~~~~~^~~~~~~~~~

ソースコード

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