#733730 (C++17) No.177 制作進行の宮森あおいです！

提出ソース

結果

問題	No.177 制作進行の宮森あおいです！
ユーザー	kkktym
提出日時	2022-01-23 16:51:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	13 ms / 2,000 ms
コード長	8,698 bytes
コンパイル時間	1,765 ms
コンパイル使用メモリ	128,588 KB
実行使用メモリ	34,904 KB
最終ジャッジ日時	2024-05-07 05:19:23
合計ジャッジ時間	2,758 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 34,648 KB
testcase_01	AC	12 ms 34,772 KB
testcase_02	AC	12 ms 34,768 KB
testcase_03	AC	12 ms 34,772 KB
testcase_04	AC	12 ms 34,772 KB
testcase_05	AC	12 ms 34,648 KB
testcase_06	AC	12 ms 34,776 KB
testcase_07	AC	12 ms 34,772 KB
testcase_08	AC	12 ms 34,900 KB
testcase_09	AC	12 ms 34,900 KB
testcase_10	AC	13 ms 34,896 KB
testcase_11	AC	12 ms 34,896 KB
testcase_12	AC	12 ms 34,904 KB
testcase_13	AC	12 ms 34,772 KB
testcase_14	AC	11 ms 34,768 KB
testcase_15	AC	12 ms 34,776 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#include <bitset>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
//#define rev(i,s,t) for(int i = s; i >= t; --i) 
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> inline int sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using PQ = priority_queue<int, vi, greater<int>>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
vi dx = {1, 0, -1, 0};
vi dy = {0, 1, 0, -1};
template<typename T>
struct Vec2 {
  T X; T Y;
  bool operator == (const Vec2& r) const { return (X == r.X && Y == r.Y); }
  bool operator != (const Vec2& r) const { return !(*this == r); }
  bool operator < (const Vec2& r) const { if(X == r.X) return Y < r.Y; return X < r.X; }
  bool operator > (const Vec2& r) const { if(X == r.X) return Y > r.Y; return X > r.X; }
};

// Modint
// modint<MOD> で宣言
template<long long MOD>
struct modint{
  long long x;
  long long mod = MOD;
  modint(long long x=0):x(x%MOD){}
  modint& operator+=(const modint a){ if((x+=a.x)>=MOD) x-=MOD; return *this; }
  modint& operator-=(const modint a){ if((x += MOD-a.x)>=MOD) x-=MOD; return *this; }
  modint& operator*=(const modint a){ (x*=a.x)%=MOD; return *this; }
  modint operator+(const modint a) const{ modint res(*this); return res+=a; }
  modint operator-(const modint a) const{ modint res(*this); return res-=a; }
  modint operator*(const modint a) const{ modint res(*this); return res*=a; }
  modint pow(long long t) const{ if(!t) return 1; modint a = pow(t>>1); a*=a; if(t&1) a*=*this; return a; }
  modint inv() const{ return pow(MOD-2); }
  modint& operator/=(const modint a){ return (*this) *= a.inv(); }
  modint operator/(const modint a) const{ modint res(*this); return res/=a; }
};
using mint = modint<1000000007>;
using mint998 = modint<998244353>;
using vm = vector<mint>;
using vmm = vector<vm>;
using vm998 = vector<mint998>;
using vmm998 = vector<vm998>;
const int NMAX=1000010; // we can calculate nCk until n is equal to NMAX
mint fact[NMAX],infac[NMAX];
void Make_Fact(){ fact[0]=fact[1]=1; for(int i=2;i<=NMAX-1;++i){ fact[i]=fact[i-1]*(mint)i;}}
void Make_InvFact(){ infac[0]=infac[1]=1; for(int i=2;i<=NMAX-1;++i){ infac[i]=infac[i-1]/(mint)i;}}
mint Comb(int n,int k){ if(n<0||k<0||n-k<0) return 0; return fact[n]*infac[k]*infac[n-k]; }

//----------------------------
// 抽象化セグ木
// 二項演算と単位元を渡して使ってね
///****例****************************
//  auto f = [&](int a,int b){ return a+b;}; // 二項演算:和
//  int id = 0; //単位元:0
//  SegTree<decltype(f),int> seg(f,id);
//************************************
//----------------------------
template <typename F,typename T>
struct SegTree{
  T identity; F merge; int size; vector<T> dat; // 二項演算merge,単位元identify
  SegTree(F f,T id):merge(f),identity(id){} // 二項演算fと単位元idを渡して宣言する
  void init(int n){ size = 1; while(size<=n) size *= 2; dat.resize(size*2-1,identity); } // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗  
  void build(vector<T> vec){ rep(i,vec.size()) dat[size-1+i] = vec[i]; dfs(0); } // 配列を渡して0(n)で初期化  
  T dfs(int k){ if(k>=size-1) return dat[k]; else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2)); }
  // index kの要素をaに変更
  void update(int k,T a){ k += size - 1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); } } 
  // index kの要素にaを加算
  void add(int k,T a){ k += size - 1; dat[k] += a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); }}
  // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size)
  T query(int a,int b,int k,int l,int r){ if(r<=a||b<=l) return identity; if(a<=l&&r<=b) return dat[k];  else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r)); }
  T query(int a,int b){ return query(a, b, 0, 0, size); }
  // デバッグ用
  void show(){ int index = 0; int num = 1; while(index<size){ rep(i,num){ if(dat[i+index]==identity) cout << "e "; else cout << dat[i+index] << " "; } cout << "\n"; num *= 2; index = index*2+1; }}
};

struct UFT{
  vector<int> par;//親
  vector<int> rank;//木の深さ
  vector<int> size;//木の大きさ
  int n;
  
  UFT(int _n) { n = _n; par.resize(n); rank.assign(n,0); size.assign(n,1); rep(i,n){ par[i] = i; }}
  //xの根を返す
  int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]);}
  //x,yを併合
  void unite(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]){
      par[x] = y;
      size[y] += size[x];
    }
    else{
      par[y] = x;
      size[x] += size[y];
      if(rank[x] == rank[y]) rank[x]++;
    }
  }
  //x,yが同じグループにいるかどうかを返す
  bool same(int x,int y) { return find(x) == find(y); }
  //xの属する木のサイズを探す
  int usize(int x) { return size[find(x)]; }
};

//****************************************
// MaxFlow
// Graph<X> gp(n);
// gp.add_edge(from, to, capacity);
// max_flow(s, t);
//****************************************

// status of edge
template <typename X>
struct Edge{
  int from, to;
  int rev;  //逆辺
  X cap; // 容量
  
  Edge() = default;

  Edge(int from, int to, int rev, X cap) : from(from), to(to), rev(rev), cap(cap) {}
};

// status of node
template <typename X>
struct Node{ 
  int idx;
  vector<Edge<X>> edge;
  //map<int,int> idtable; // map[to] = val: node[idx]からnode[to]に出るedgeのindexを返す
  
  Node() = default;

  explicit Node(int idx) : idx(idx) {}
};

template <typename X>
class Graph{
private:
  int n; // number of node
  int m; // number of edge
  vector<Node<X>> node; 
  X inf = numeric_limits<X>::max();
  
  void Init_Node() {
    rep(i,n) node.emplace_back(i);
  }
public:
  explicit Graph(int n) : n(n) {
    Init_Node();
  }

  // 容量cap の辺を追加
  void add_edge(int from, int to, X cap) { 
    node[from].edge.emplace_back(from, to, node[to].edge.size(), cap);
    //node[from].idtable[to] = node[from].edge.size() - 1;
    node[to].edge.emplace_back(to, from, node[from].edge.size() - 1, 0);
    //node[to].idtable[from] = node[to].edge.size() - 1;    
  }

  // from->toの辺(Edge<>)を返す
  // Edge<X> get_edge(int from, int to) {
  //   return node[from].edge[node[from].idtable[to]];
  // }

  // s->tの最大流
  X max_flow(int s, int t) {
    vi level(n);
    vi iter(n);
    auto bfs = [&]() {
		 level.assign(n, -1);
		 queue<int> q;
		 level[s] = 0;
		 q.push(s);
		 while( !q.empty() ) {
		   int v = q.front(); q.pop();
		   for(auto next: node[v].edge) {
		     if(next.cap > 0 && level[next.to] < 0) {
		       level[next.to] = level[v] + 1;
		       q.push(next.to);
		     }
		   }
		 }
		 
	       };


    auto dfs = [&](auto func, int v, X f) {
		 if(v == t) return f;
		 for(int &i = iter[v]; i < node[v].edge.size(); ++i) {
		   Edge<X> &e = node[v].edge[i];
		   if(e.cap > 0 && level[v] < level[e.to]) {
		     X d = func(func, e.to, min(f, e.cap));
		     if(d > 0) {
		       e.cap -= d;
		       node[e.to].edge[e.rev].cap += d;
		       return d;
		     }
		   }
		 }
		 return (X)0;
	       };
    
    // main
    X flow = 0;
    for(;;) {
      bfs();
      if(level[t] < 0) return flow;
      iter.assign(n, 0);
      X f;
      while((f = dfs(dfs, s, inf)) > 0) {
	flow += f;
      }
    }
  }

};


void Solve(){
  int w; cin >> w;
  int n,m; cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  cin >> m;
  vi c(m);
  rep(i,m) cin >> c[i];
  vector<map<int,int>> mp(m);
  rep(i,m) {
    int q; cin >> q;
    rep(j,q) {
      int x; cin >> x;
      x--;
      mp[i][x] = 1;
    }
  }
  Graph<int> gp(n*2+m*2+2);
  rep(i,n) {
    gp.add_edge(i, n+m+i, a[i]);
    gp.add_edge(2*n+2*m, i, inf);
  }
  rep(i,m) {
    gp.add_edge(n+i, 2*n+m+i, c[i]);
    gp.add_edge(2*n+m+i, 2*n+2*m+1, inf);
  }
  rep(i,n) {
    rep(j,m) {
      if(mp[j].find(i) == mp[j].end()) {
        gp.add_edge(n+m+i, n+j, inf);
      }
    }
  }
  int res = gp.max_flow(2*n+2*m, 2*n+2*m+1);
  cout << (res >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << "\n";

}
int main()
{
  Solve();
  return 0;
}

yukicoder

結果

テストケース

ソースコード