結果
問題 |
No.3173 じゃんけんの勝ちの回数
|
ユーザー |
![]() |
提出日時 | 2025-06-06 22:09:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 2,524 bytes |
コンパイル時間 | 3,180 ms |
コンパイル使用メモリ | 284,672 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-06-06 22:09:43 |
合計ジャッジ時間 | 5,854 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:73:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 73 | g[1][4]=2e18; | ^~~~ main.cpp:74:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 74 | g[1][6]=2e18; | ^~~~ main.cpp:75:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 75 | g[2][4]=2e18; | ^~~~ main.cpp:76:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 76 | g[2][5]=2e18; | ^~~~ main.cpp:77:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 77 | g[3][5]=2e18; | ^~~~ main.cpp:78:17: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 78 | g[3][6]=2e18; | ^~~~ main.cpp:88:18: warning: overflow in conversion from ‘double’ to ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow] 88 | g1[1][5]=2e18; | ^~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; typedef int Vert; typedef int Capacity; typedef vector< vector<Vert> > Layer; typedef vector< vector<Capacity> > Graph; // 「v からはじまる」「it~end の辺を使った」パスを作ってそこに流せるだけ流す Capacity dfs( Graph& G, Vert v, Layer::iterator it, Layer::iterator end, Capacity mf = numeric_limits<Capacity>::max() ) { if( it == end ) return mf; for(int i=0; i!=it->size(); ++i) if( G[v][(*it)[i]] ) if( Capacity f = dfs(G, (*it)[i], it+1, end, min(mf,G[v][(*it)[i]]) ) ) { G[v][(*it)[i]] -= f; G[(*it)[i]][v] += f; return f; } return 0; } Capacity dinic( Graph& G, int Src, int Dest ) { for( Capacity totalFlow = 0 ;; ) { // L[k] == Src から k ステップで行ける頂点の集合。BFSで求める。 Layer L(1); L.back() = vector<Vert>(1,Src); vector<bool> reached(G.size()); reached[Src] = true; while( !reached[Dest] && !L.back().empty() ) { L.resize( L.size()+1 ); vector<Vert> &l0=L[L.size()-2], &l1=L[L.size()-1]; for(int i=0; i!=l0.size(); ++i) for(Vert u=0; u!=G.size(); ++u) if( G[l0[i]][u] && !reached[u] ) l1.push_back(u), reached[u]=true; } L.back() = vector<Vert>(1, Dest); // Dest までたどりつけなくなったので最大流の計算完了 if( !reached[Dest] ) return totalFlow; // たどりつける場合はDFSで流しまくる while( int f = dfs(G, Src, L.begin()+1, L.end()) ) totalFlow += f; } } int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int T; cin>>T; for(int z=1;z<=T;z++){ ll A1,A2,A3,B1,B2,B3; cin>>A1>>A2>>A3>>B1>>B2>>B3; Graph g(8,vector<Capacity>(8)); g[0][1]=A1; g[0][2]=A2; g[0][3]=A3; g[1][4]=2e18; g[1][6]=2e18; g[2][4]=2e18; g[2][5]=2e18; g[3][5]=2e18; g[3][6]=2e18; g[4][7]=B1; g[5][7]=B2; g[6][7]=B3; ll all=A1+A2+A3; cout<<all-dinic(g,0,7)<<" "; Graph g1(8,vector<Capacity>(8)); g1[0][1]=A1; g1[0][2]=A2; g1[0][3]=A3; g1[1][5]=2e18; g1[2][6]=2e18; g1[3][4]=2e18; g1[4][7]=B1; g1[5][7]=B2; g1[6][7]=B3; cout<<dinic(g1,0,7)<<"\n"; } }