結果
問題 |
No.3173 じゃんけんの勝ちの回数
|
ユーザー |
|
提出日時 | 2025-06-06 22:17:56 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 6,436 bytes |
コンパイル時間 | 11,432 ms |
コンパイル使用メモリ | 171,208 KB |
実行使用メモリ | 214,688 KB |
最終ジャッジ日時 | 2025-06-06 22:18:18 |
合計ジャッジ時間 | 13,567 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (113 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); public static void Main() { Solve(); } static void Solve() { var t = NN; var ans = new int[t][]; for (var u = 0; u < t; ++u) { var a = NList; var b = NList; ans[u] = new int[] { GetMin(a, b), Math.Min(a[0], b[1]) + Math.Min(a[1], b[2]) + Math.Min(a[2], b[0]), }; } WriteLine(string.Join("\n", ans.Select(ai => string.Join(" ", ai)))); } static int GetMin(int[] a, int[] b) { var g = new MaxFlowGraph(8); var INF = int.MaxValue; g.AddEdge(0, 1, a[0]); g.AddEdge(0, 2, a[1]); g.AddEdge(0, 3, a[2]); g.AddEdge(1, 4, INF); g.AddEdge(1, 6, INF); g.AddEdge(2, 4, INF); g.AddEdge(2, 5, INF); g.AddEdge(3, 5, INF); g.AddEdge(3, 6, INF); g.AddEdge(4, 7, b[0]); g.AddEdge(5, 7, b[1]); g.AddEdge(6, 7, b[2]); return a[0] + a[1] + a[2] - (int)g.Flow(0, 7); } class MaxFlowGraph { int _n; long max = long.MaxValue; class EdgeI { public int to { get; private set; } public int rev { get; private set; } public long cap { get; set; } public EdgeI(int to, int rev, long cap) { this.to = to; this.rev = rev; this.cap = cap; } } List<KeyValuePair<int, int>> pos = new List<KeyValuePair<int, int>>(); List<EdgeI>[] g; public MaxFlowGraph(int n) { _n = n; g = new List<EdgeI>[n]; for (var i = 0; i < n; ++i) g[i] = new List<EdgeI>(); } public int AddEdge(int from, int to, long cap) { var m = pos.Count; pos.Add(new KeyValuePair<int, int>(from, g[from].Count)); g[from].Add(new EdgeI(to, g[to].Count, cap)); g[to].Add(new EdgeI(from, g[from].Count - 1, 0)); return m; } public class Edge { public int from { get; private set; } public int to { get; private set; } public long cap { get; private set; } public long flow { get; private set; } public Edge(int from, int to, long cap, long flow) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; } } public Edge GetEdge(int i) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; return new Edge(pos[i].Key, e.to, e.cap + re.cap, re.cap); } public List<Edge> GetEdges() { var m = pos.Count; var result = new List<Edge>(); for (var i = 0; i < m; ++i) result.Add(GetEdge(i)); return result; } public void ChangeEdge(int i, long new_cap, long new_flow) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; e.cap = new_cap - new_flow; re.cap = new_flow; } public long Flow(int s, int t) { return Flow(s, t, max); } public long Flow(int s, int t, long limit) { var level = new int[_n]; var iter = new int[_n]; var que = new Queue<int>(); void bfs() { for (var i = 0; i < _n; ++i) level[i] = -1; level[s] = 0; que.Clear(); que.Enqueue(s); while (que.Count > 0) { var v = que.Dequeue(); foreach (var e in g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.Enqueue(e.to); } } } long dfs(int v, long up) { if (v == s) return up; long res = 0; var level_v = level[v]; for (var i = iter[v]; i < g[v].Count; ++i) { var e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; long d = dfs(e.to, Min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) break; } return res; } long flow = 0; while (flow < limit) { bfs(); if (level[t] == -1) break; for (var i = 0; i < iter.Length; ++i) iter[i] = 0; while (flow < limit) { var f = dfs(t, limit - flow); if (f == 0) break; flow += f; } } return flow; } long Min(long a, long b) { return a.CompareTo(b) < 0 ? a : b; } public bool[] MinCut(int s) { var visited = new bool[_n]; var que = new Queue<int>(); que.Enqueue(s); while (que.Count > 0) { var p = que.Dequeue(); visited[p] = true; foreach (var e in g[p]) { if (e.cap != 0 && !visited[e.to]) { visited[e.to] = true; que.Enqueue(e.to); } } } return visited; } } }