結果

問題 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;
      |                  ^~~

ソースコード

diff # 

#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";
    }
}
0