結果
問題 | No.2713 Just Solitaire |
ユーザー | bluebery1001 |
提出日時 | 2024-03-31 14:56:35 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 20,693 bytes |
コンパイル時間 | 4,584 ms |
コンパイル使用メモリ | 289,936 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-30 20:07:25 |
合計ジャッジ時間 | 5,266 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 3 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 3 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 3 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 3 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,824 KB |
testcase_19 | AC | 3 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,824 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,820 KB |
testcase_24 | AC | 3 ms
6,820 KB |
testcase_25 | AC | 2 ms
6,816 KB |
testcase_26 | AC | 3 ms
6,816 KB |
testcase_27 | AC | 3 ms
6,820 KB |
testcase_28 | AC | 3 ms
6,820 KB |
testcase_29 | AC | 3 ms
6,816 KB |
testcase_30 | AC | 3 ms
6,820 KB |
testcase_31 | AC | 3 ms
6,820 KB |
testcase_32 | AC | 3 ms
6,820 KB |
testcase_33 | AC | 3 ms
6,820 KB |
ソースコード
using namespace std; #include<bits/stdc++.h> void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(30);_main();return 0;} typedef long long ll;typedef long double ld; typedef unsigned long long ull; typedef unsigned int uint; typedef string str; #define rep1(a) for(ll i = 0; i < (a); i++) #define rep2(i, a) for(ll i = 0; i < (a); i++) #define rep3(i, a, b) for(ll i = (a); i < (b); i++) #define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define ALL(x) std::begin(x),std::end(x) #define rALL(x) std::rbegin(x),std::rend(x) #define INF ((1LL<<62)-(1LL<<31)) #define bit(x,i) (((x)>>(i))&1) #define fi first #define se second #define pb push_back #define Endl endl #define spa " " #define YesNo(x) cout<<(x?"Yes":"No")<<endl; #define eps (1e-10) //コンパイル時の引数にBLUEBERRYを渡すとdeb関数が使える #ifdef BLUEBERRY #define deb print // #define _GLIBCXX_DEBUG #else #define deb(...) //速くなる呪文 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif //!?!? #define O print //可変長引数で入力を受け取りつつ変数を宣言 inline void scan(){} template<class Head,class... Tail> inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);} #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) //vectorのcin template<typename T> std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;} //vectorのcout template<typename T> std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;} //x,y,x,yを渡すとldで距離を返す long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));} //可変長引数のprint関数 void print(){cout << '\n';} template<class T, class... Ts> void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} //可変長引数のmin template<class... T> constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});} //可変長引数のmax template<class... T> constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});} template<typename T,typename U>inline bool chmax(T&a,U b){if(a<b){a=b;return 1;}return 0;} template<typename T,typename U>inline bool chmin(T&a,U b){if(a>b){a=b;return 1;}return 0;} template<typename T> inline T sum(vector<T>&a){T ret{};for(auto&i:a)ret+=i;return ret;} template<typename T> inline T min(vector<T>&a){T ret=a[0];for(auto&i:a)chmin(ret,i);return ret;} template<typename T> inline T max(vector<T>&a){T ret=a[0];for(auto&i:a)chmax(ret,i);return ret;} template<typename T> inline int len(vector<T>&a){return a.size();} inline int len(string&a){return a.size();} // n次元配列の初期化。第2引数の型のサイズごとに初期化していく。 template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){std::fill( (T*)array, (T*)(array+N), val );} //こめんとを付け外ししてMODを切り替える //ll MOD = INF; // ll MOD = 1000000007; ll MOD = 998244353; //from:https://kenkoooo.hatenablog.com/entry/2016/11/30/163533 int128 // std::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s){__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do{--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;} // __int128 parsetoint128(string &s) {__int128 ret = 0;for (int i = 0; i < (int)s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret=10*ret+(__int128_t)(s[i]-'0');return ret;} ll divide(ll a, ll b){if(b < 0) a *= -1, b *= -1;if(a >= 0) return a/b;else return -(((-a)+(b-1))/b);} //回文判定 // bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;} //オイラー数を計算する関数 int phi(int n){int ans=n;for(int p=2;p*p<=n;p++)if(n%p==0){while(n%p==0)n/=p;ans-=ans/p;}if(n!=1)ans-=ans/n;return ans;} //二部グラフ判定 重みなしグラフを引数に取り、boolを返す // bool isbipartite_graph(vector<vector<ll>>&g){ll v = g.size();vector<ll>col(v,-1);vector<bool>used(v,false);bool ret = true;rep(i,v){if(used[i])continue;col[i]=0;[DFS([&](auto&&f,ll pos,ll pr)->void{if(used[pos])return;used[pos]=true;for(auto to:g[pos]){if(to==pr)continue;if(used[to]&&col[pos]==col[to]){ret = false;return;}if(used[to])continue;col[to]=col[pos]^1;f(f,to,pos);}}),&i]{DFS(DFS,i,-1);}();}return ret;} //a~bの和 a<b ll ran(ll a,ll b){return ((a+b)*(b-a+1))/2;} //座圧する ll zaatu(vector<ll>&A){map<ll,ll>m;for(auto&&x:A)m[x]=0;ll ret = 0;for(auto&&[key,val]:m)val=ret++;for(auto&&x:A)x=m[x];return ret;} //約数列挙 引数に取った整数の約数のvectorを返す vector<ll>enumdiv(ll n){vector<ll>s;for(ll i = 1;i*i<=n;i++){if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}}return s;} //トポロジカルソート グラフ、入次数カウント、頂点数を引数で渡すと、トポロジカルソートされた頂点列を返す vector<ll> topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,ll v){vector<ll>ret;priority_queue<ll,vector<ll>,greater<ll>>pq;rep(i,0,v){if(nyu_cnt[i]==0)pq.push(i);}while(!pq.empty()){ll pos = pq.top();pq.pop();for(ll i:G[pos]){nyu_cnt[i]--;if(nyu_cnt[i]==0)pq.push(i);}ret.push_back(pos);}return ret;} //素因数分解 pair<素数、指数>のvectorを返す vector<pair<ll,ll>> soinsu_bunkai(ll x){vector<pair<ll,ll>>ret;rep(i,2,sqrt(x)+1){if(x%i==0){ll cnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}}if(x!=1)ret.push_back({x,1});return ret;} //二項係数MOD MODは上の方で設定、MAXまでのnCrをCOM(n,r)でとれる const int MAX = 5000010; ll fac[MAX], finv[MAX], invv[MAX]; void COMinit(){fac[0]=fac[1]=finv[0]=finv[1]=invv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%MOD;invv[i]=MOD-invv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*invv[i]%MOD;}} ll COM(int n,int k){if(n<k)return 0;if(n<0||k<0)return 0;if(k==0)return 1;return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;} ll nPr(int n,int k){if(n<k)return 0;if(n<0||k<0)return 0;if(k==0)return 1;return fac[n]*(finv[n-k]);} //エラトステネスの篩 isprimeには素数かどうかが入っている vector<bool> isprime;vector<int> Era(int n) {isprime.resize(n, true);vector<int> res;isprime[0] = false; isprime[1] = false;for (int i = 2; i < n; ++i) isprime[i] = true;for (int i = 2; i < n; ++i){if (isprime[i]) {res.push_back(i);for (int j = i*2; j < n; j += i) isprime[j] = false;}}return res;} //Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find class UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;}; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; //グリッドの8近傍 4まで回せば4近傍 ll dx[8] = {0,1,0,-1,-1,-1,1,1},dy[8]={1,0,-1,0,-1,1,-1,1}; template <class F> ll bin_search(ll ok,ll ng,const F&f){while(abs(ok-ng)>1){long long mid=(ok+ng)>>1;(f(mid)?ok:ng)=mid;}return ok;} bool solve(); void _main(){ []{[]{[]{[]{[]{}();}();}();}();}(); int testcase = 1; // cin >> testcase; for(;testcase--;){ if(solve()){ // O("Yes"); } else{ // O("-1"); // O("No"); } } cout<<flush; []{[]{[]{[]{[]{}();}();}();}();}(); } // #include<atcoder/modint> // using namespace atcoder; // using mint = modint998244353; // using mint1 = modint1000000007; // ld cps = CLOCKS_PER_SEC; // ld now = clock(); #include <algorithm> #include <cassert> #include <limits> #include <queue> #include <vector> #include <algorithm> #include <utility> #include <vector> namespace atcoder { namespace internal { template <class E> struct csr { std::vector<int> start; std::vector<E> elist; explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } }; } // namespace internal } // namespace atcoder #include <vector> namespace atcoder { namespace internal { template <class T> struct simple_queue { std::vector<T> payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return int(payload.size()) - pos; } bool empty() const { return pos == int(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } // namespace internal } // namespace atcoder namespace atcoder { template <class Cap, class Cost> struct mcf_graph { public: mcf_graph() {} explicit mcf_graph(int n) : _n(n) {} int add_edge(int from, int to, Cap cap, Cost cost) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); assert(0 <= cost); int m = int(_edges.size()); _edges.push_back({from, to, cap, 0, cost}); return m; } struct edge { int from, to; Cap cap, flow; Cost cost; }; edge get_edge(int i) { int m = int(_edges.size()); assert(0 <= i && i < m); return _edges[i]; } std::vector<edge> edges() { return _edges; } std::pair<Cap, Cost> flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) { return slope(s, t, flow_limit).back(); } std::vector<std::pair<Cap, Cost>> slope(int s, int t) { return slope(s, t, std::numeric_limits<Cap>::max()); } std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); int m = int(_edges.size()); std::vector<int> edge_idx(m); auto g = [&]() { std::vector<int> degree(_n), redge_idx(m); std::vector<std::pair<int, _edge>> elist; elist.reserve(2 * m); for (int i = 0; i < m; i++) { auto e = _edges[i]; edge_idx[i] = degree[e.from]++; redge_idx[i] = degree[e.to]++; elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}}); elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}}); } auto _g = internal::csr<_edge>(_n, elist); for (int i = 0; i < m; i++) { auto e = _edges[i]; edge_idx[i] += _g.start[e.from]; redge_idx[i] += _g.start[e.to]; _g.elist[edge_idx[i]].rev = redge_idx[i]; _g.elist[redge_idx[i]].rev = edge_idx[i]; } return _g; }(); auto result = slope(g, s, t, flow_limit); for (int i = 0; i < m; i++) { auto e = g.elist[edge_idx[i]]; _edges[i].flow = _edges[i].cap - e.cap; } return result; } private: int _n; std::vector<edge> _edges; struct _edge { int to, rev; Cap cap; Cost cost; }; std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g, int s, int t, Cap flow_limit) { std::vector<std::pair<Cost, Cost>> dual_dist(_n); std::vector<int> prev_e(_n); std::vector<bool> vis(_n); struct Q { Cost key; int to; bool operator<(Q r) const { return key > r.key; } }; std::vector<int> que_min; std::vector<Q> que; auto dual_ref = [&]() { for (int i = 0; i < _n; i++) { dual_dist[i].second = std::numeric_limits<Cost>::max(); } std::fill(vis.begin(), vis.end(), false); que_min.clear(); que.clear(); size_t heap_r = 0; dual_dist[s].second = 0; que_min.push_back(s); while (!que_min.empty() || !que.empty()) { int v; if (!que_min.empty()) { v = que_min.back(); que_min.pop_back(); } else { while (heap_r < que.size()) { heap_r++; std::push_heap(que.begin(), que.begin() + heap_r); } v = que.front().to; std::pop_heap(que.begin(), que.end()); que.pop_back(); heap_r--; } if (vis[v]) continue; vis[v] = true; if (v == t) break; Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second; for (int i = g.start[v]; i < g.start[v + 1]; i++) { auto e = g.elist[i]; if (!e.cap) continue; Cost cost = e.cost - dual_dist[e.to].first + dual_v; if (dual_dist[e.to].second - dist_v > cost) { Cost dist_to = dist_v + cost; dual_dist[e.to].second = dist_to; prev_e[e.to] = e.rev; if (dist_to == dist_v) { que_min.push_back(e.to); } else { que.push_back(Q{dist_to, e.to}); } } } } if (!vis[t]) { return false; } for (int v = 0; v < _n; v++) { if (!vis[v]) continue; dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second; } return true; }; Cap flow = 0; Cost cost = 0, prev_cost_per_flow = -1; std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}}; while (flow < flow_limit) { if (!dual_ref()) break; Cap c = flow_limit - flow; for (int v = t; v != s; v = g.elist[prev_e[v]].to) { c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap); } for (int v = t; v != s; v = g.elist[prev_e[v]].to) { auto& e = g.elist[prev_e[v]]; e.cap += c; g.elist[e.rev].cap -= c; } Cost d = -dual_dist[s].first; flow += c; cost += c * d; if (prev_cost_per_flow == d) { result.pop_back(); } result.push_back({flow, cost}); prev_cost_per_flow = d; } return result; } }; } // namespace atcoder #include <algorithm> #include <cassert> #include <limits> #include <queue> #include <vector> namespace atcoder { template <class Cap> struct mf_graph { public: mf_graph() : _n(0) {} explicit mf_graph(int n) : _n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = int(pos.size()); pos.push_back({from, int(g[from].size())}); int from_id = int(g[from].size()); int to_id = int(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = int(pos.size()); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } std::vector<edge> edges() { int m = int(pos.size()); std::vector<edge> result; for (int i = 0; i < m; i++) { result.push_back(get_edge(i)); } return result; } void change_edge(int i, Cap new_cap, Cap new_flow) { int m = int(pos.size()); assert(0 <= i && i < m); assert(0 <= new_flow && new_flow <= new_cap); auto& _e = g[pos[i].first][pos[i].second]; auto& _re = g[_e.to][_e.rev]; _e.cap = new_cap - new_flow; _re.cap = new_flow; } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector<int> level(_n), iter(_n); internal::simple_queue<int> que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < int(g[v].size()); i++) { _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) return res; } level[v] = _n; return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } return flow; } std::vector<bool> min_cut(int s) { std::vector<bool> visited(_n); internal::simple_queue<int> que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto e : g[p]) { if (e.cap && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } private: int _n; struct _edge { int to, rev; Cap cap; }; std::vector<std::pair<int, int>> pos; std::vector<std::vector<_edge>> g; }; } // namespace atcoder using namespace atcoder; bool solve(){ LL(n,m); vector<ll>a(n);cin >> a; vector<ll>b(m);cin >> b; mf_graph<ll>g(n+m+2); ll S = 0,G = 1; ll X = 1000000000; //カードの頂点 //訪れると+a[i]+X、訪れないとX //ボーナスの頂点 //訪れると+b[i]+X、訪れないとXだが //ボーナスの頂点を訪れたうえで含まれるカードに訪れないはだめ //罰金にしたい rep(i,n){ g.add_edge(S,i+2,X); g.add_edge(i+2,G,X+a[i]); } rep(i,m){ LL(k); vector<ll>c(k);cin >> c; for(auto j:c){ g.add_edge(n+2+i,j+1,INF); } g.add_edge(S,n+2+i,b[i]+X); g.add_edge(n+2+i,G,X); } auto ret = g.flow(S,G); O(sum(b)+X*(n+m)-ret); return 0; }