結果

問題 No.3173 じゃんけんの勝ちの回数
ユーザー The Forsaking
提出日時 2025-06-06 21:42:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,800 bytes
コンパイル時間 1,937 ms
コンパイル使用メモリ 197,460 KB
実行使用メモリ 18,256 KB
最終ジャッジ日時 2025-06-06 21:42:50
合計ジャッジ時間 5,467 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:91:50: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |                 for (int i = 1; i < 4; i++) scanf("%d", a + i), add(0, i, a[i], 0);
      |                                             ~~~~~^~~~~~~~~~~~~
main.cpp:92:50: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |                 for (int i = 1; i < 4; i++) scanf("%d", b + i), add(i + 3, et, b[i], 0);
      |                                             ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000008, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];

int a[4], b[4];
int e[N], ne[N], h[N], idx, d[N], inc[N], pre[N], v[N];
bool st[N];
int s = 0, et = 7;

void add(int a, int b, int c, int d) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, v[idx] = d, h[a] = idx++;
	e[idx] = a, ne[idx] = h[b], w[idx] = 0, v[idx] = -d, h[b] = idx++;
}

bool spfa() {
	queue<int> q;
	// memset(d, -0x3f, sizeof(int) * (n + 10));
    memset(d, 0x3f, sizeof(int) * (20));
    q.push(s), d[s] = 0, inc[s] = INF;

    while (q.size()) {
        int u = q.front();
        q.pop(); st[u] = 0;

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (w[i] && d[j] > d[u] + v[i]) {
                d[j] = d[u] + v[i], pre[j] = i, inc[j] = min(inc[u], w[i]);
                if (!st[j]) q.push(j), st[j] = 1;
            }
        }
    }
    return d[et] != INF;
}

void ek(int& f, int& c) {
    f = c = 0;
    while (spfa()) {
        int t = inc[et];
        f += t, c += t * d[et];
        for (int i = et; i != s; i = e[pre[i] ^ 1]) {
            w[pre[i]] -= t, w[pre[i] ^ 1] += t;
        }
    }
}

bool spfa2() {
	queue<int> q;
	memset(d, -0x3f, sizeof(int) * (n + 10));
    q.push(s), d[s] = 0, inc[s] = INF;

    while (q.size()) {
        int u = q.front();
        q.pop(); st[u] = 0;

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (w[i] && d[j] < d[u] + v[i]) {
                d[j] = d[u] + v[i], pre[j] = i, inc[j] = min(inc[u], w[i]);
                if (!st[j]) q.push(j), st[j] = 1;
            }
        }
    }
	return d[et] >= 0;
}

void ek2(int& f, int& c) {
    f = c = 0;
    while (spfa2()) {
        int t = inc[et];
        f += t, c += t * d[et];
        for (int i = et; i != s; i = e[pre[i] ^ 1]) {
            w[pre[i]] -= t, w[pre[i] ^ 1] += t;
        }
    }
}


int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(h, -1, sizeof(int) * (20));
		idx = 0;
		for (int i = 1; i < 4; i++) scanf("%d", a + i), add(0, i, a[i], 0);
		for (int i = 1; i < 4; i++) scanf("%d", b + i), add(i + 3, et, b[i], 0);
		for (int i = 1; i < 4; i++) {
			for (int j = 1; j < 4; j++) {
				if (i + 1 == j || (i == 3 && j == 1)) add(i, j + 3, INF, 1);
				else add(i, j + 3, INF, 0);
			}
		}
		int f, c;
		ek(f, c);
		printf("%d ", c);
		memset(h, -1, sizeof(int) * (20));
		idx = 0;
		for (int i = 1; i < 4; i++) add(0, i, a[i], 0);
		for (int i = 1; i < 4; i++) add(i + 3, et, b[i], 0);
		for (int i = 1; i < 4; i++) {
			for (int j = 1; j < 4; j++) {
				if (i + 1 == j || (i == 3 && j == 1)) add(i, j + 3, INF, 1);
				else add(i, j + 3, INF, 0);
			}
		}
		ek2(f, c);
		printf("%d\n", c);
	}
	return 0;
}
0