結果

問題 No.3173 じゃんけんの勝ちの回数
コンテスト
ユーザー ZeriToki
提出日時 2025-06-06 22:09:35
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,524 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,159 ms
コンパイル使用メモリ 343,144 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-11 06:22:08
合計ジャッジ時間 4,959 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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