結果

問題 No.3173 じゃんけんの勝ちの回数
ユーザー umezo
提出日時 2025-06-07 03:02:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 2,087 bytes
コンパイル時間 4,114 ms
コンパイル使用メモリ 286,688 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-06-07 03:02:59
合計ジャッジ時間 5,604 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(v) v.begin(),v.end()
using u128=__int128_t;
using ll=long long;

typedef pair<int,int> pii;
const int INF=1e9+7;

struct edge{int to,cap,cost,rev;};

int V=8;
const int MAX=10;
vector<edge> G[MAX];
int h[MAX];
int dist[MAX];
int prevv[MAX],preve[MAX];

void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
  G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}

int min_cost_flow(int s,int t,int f){
  int res=0;
  fill(h,h+V,0);
  while(f>0){
    priority_queue<pii,vector<pii>,greater<pii>> que;
    fill(dist,dist+V,INF);
    dist[s]=0;
    que.push(pii(0,s));
    while(!que.empty()){
      pii p=que.top(); que.pop();
      int v=p.second;
      if(dist[v]<p.first) continue;
      rep(i,G[v].size()){
        edge &e=G[v][i];
        if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
          dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
          prevv[e.to]=v;
          preve[e.to]=i;
          que.push(pii(dist[e.to],e.to));
        }
      }
    }
    if(dist[t]==INF) return -1;
    rep(v,V) h[v]+=dist[v];
    
    int d=f;
    for(int v=t;v!=s;v=prevv[v]) d=min(d,G[prevv[v]][preve[v]].cap);
    f-=d;
    res+=d*h[t];
    for(int v=t;v!=s;v=prevv[v]){
      edge &e=G[prevv[v]][preve[v]];
      e.cap-=d;
      G[v][e.rev].cap+=d;
    }
  }
  return res;
}
 
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int T;
  cin>>T;
  while(T--){
    vector<ll> A(3),B(3);
    rep(i,3) cin>>A[i];
    rep(i,3) cin>>B[i];
    ll ma=0;
    rep(i,3) ma+=min(A[i],B[(i+1)%3]);
    
    rep(i,MAX){
      G[i].clear();
      h[i]=0;
      dist[i]=0;
      prevv[i]=0;
      preve[i]=0;
    }
    int s=6,t=7;
    rep(i,3) add_edge(s,i,A[i],0);
    rep(i,3) add_edge(i+3,t,B[i],0);
    rep(i,3) rep(j,3){
      if((i+1)%3==j) continue;
      add_edge(i,j+3,INF,0);
    }
    add_edge(s,t,INF,1);
    int mi=min_cost_flow(s,t,A[0]+A[1]+A[2]);
    cout<<mi<<" "<<ma<<'\n';
  }
  
  return 0;
}
0