結果
問題 | No.2638 Initial fare |
ユーザー |
|
提出日時 | 2024-02-19 22:57:23 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,682 bytes |
コンパイル時間 | 13,786 ms |
コンパイル使用メモリ | 167,336 KB |
実行使用メモリ | 400,844 KB |
最終ジャッジ日時 | 2024-10-07 23:45:03 |
合計ジャッジ時間 | 37,870 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 TLE * 1 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (103 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
namespace AtCoder;#nullable enableusing System.Numerics;static class Extensions{public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();}class Graph<T>{public struct Edge{public int Ab { get; set; }public int Ad { get; set; }public T Distance { get; set; }}public int N { get; private init; }public bool Directed { get; private init; }public List<List<(int next, int edgeIndex)>> AdjacencyList { get; private init; }public List<Edge> Edges { get; private init; }public Graph(int verticals, IReadOnlyList<Edge> edges, bool directed){N = verticals;Directed = directed;AdjacencyList = new List<List<(int, int)>>();for (var i = 0; i < N; i++) AdjacencyList.Add(new List<(int, int)>());Edges = new List<Edge>();for (var i = 0; i < edges.Count; i++){var edge = edges[i];Edges.Add(edge);AdjacencyList[edge.Ab].Add((edge.Ad, i));if (!Directed) AdjacencyList[edge.Ad].Add((edge.Ab, i));}}}class GraphBuilder{public static Graph<int> SimpleGraph(int verticals, (int ab, int ad)[] edges, bool directed){var e = edges.Select(e => new Graph<int>.Edge { Ab = e.ab, Ad = e.ad, Distance = 1 }).ToList();return new(verticals, e, directed);}public static Graph<T> Graph<T>(int verticals, (int ab, int ad, T edge)[] edges, bool directed){var e = edges.Select(e => new Graph<T>.Edge { Ab = e.ab, Ad = e.ad, Distance = e.edge }).ToList();return new(verticals, e, directed);}}class GraphBase<T> { public required Graph<T> Graph { get; init; } }class Tree<T> : GraphBase<T>{public static Tree<T>? TryConstruct(Graph<T> graph){if (graph.Directed || graph.Edges.Count + 1 != graph.N) return null;var visited = new bool[graph.N];int S(int v, int prev){visited[v] = true;var res = 1;foreach (var (next, _) in graph.AdjacencyList[v]){if (next == prev || visited[next]) continue;res += S(next, v);}return res;}if (S(0, -1) < graph.N) return null;return new Tree<T> { Graph = graph };}public interface IRerootingOperator<TResult>{TResult Identity { get; }TResult Merge(TResult l, TResult r);TResult Finalize(TResult e, int v);}public TResult[] Rerooting<TResult, TOperator>(TOperator op = default) where TOperator : struct, IRerootingOperator<TResult>{var n = Graph.N;var res = new TResult[n];var adjacencyList = Graph.AdjacencyList;var subTreeValues = new (TResult, int)[n][];TResult SubTreeValue(int v, int prev){var merged = op.Identity;var l = adjacencyList[v].Count;subTreeValues[v] = new (TResult, int)[l];for (var i = 0; i < l; i++){var (next, index) = adjacencyList[v][i];if (next == prev) continue;var subTreeValue = SubTreeValue(next, v);subTreeValues[v][i] = (subTreeValue, index);merged = op.Merge(merged, subTreeValue);}return op.Finalize(merged, v);}void Evaluate(int v, int prev, TResult prevValue){var adjacencies = adjacencyList[v];var l = adjacencies.Count;for (var i = 0; i < l; i++) if (adjacencies[i].next == prev){subTreeValues[v][i].Item1 = prevValue;break;}var sumL = new TResult[l];var sumR = new TResult[l];sumL[0] = op.Identity;sumR[l - 1] = op.Identity;for (var i = 1; i < l; i++) sumL[i] = op.Merge(sumL[i - 1], subTreeValues[v][i - 1].Item1);for (var i = l - 2; i >= 0; i--) sumR[i] = op.Merge(sumR[i + 1], subTreeValues[v][i + 1].Item1);res[v] = op.Finalize(op.Merge(sumR[0], subTreeValues[v][0].Item1), v);for (var i = 0; i < l; i++){var next = adjacencies[i].next;if (next == prev) continue;Evaluate(next, v, op.Finalize(op.Merge(sumL[i], sumR[i]), next));}}SubTreeValue(0, -1);Evaluate(0, -1, op.Identity);return res;}}readonly struct Op : Tree<int>.IRerootingOperator<long[]>{public long[] Identity => new long[4];public long[] Finalize(long[] e, int v){var res = new long[4];res[0] = 1;for (var i = 1; i <= 3; i++) res[i] += e[i - 1];return res;}public long[] Merge(long[] l, long[] r){var y = new long[4];for (var i = 0; i <= 3; i++) y[i] = l[i] + r[i];return y;}}class AtCoder{object? Solve(){var n = Int();var edges = (n - 1).Repeat(() => (Int() - 1, Int() - 1));var g = GraphBuilder.SimpleGraph(n, edges, false);var t = Tree<int>.TryConstruct(g)!;var s = t.Rerooting<long[], Op>();var ans = 0L;for (var i = 0; i < n; i++) for (var j = 1; j <= 3; j++) ans += s[i][j];ans /= 2;return ans;}public static void Main() => new AtCoder().Run();public void Run(){var res = Solve();if (res != null){if (res is bool yes) res = yes ? "Yes" : "No";sw.WriteLine(res);}sw.Flush();}string[] input = Array.Empty<string>();int iter = 0;readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };#pragma warning disable IDE0051string String(){while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);return input[iter++];}T Input<T>() where T : IParsable<T> => T.Parse(String(), null);int Int() => Input<int>();void Out(object? x, string? separator = null){separator ??= Environment.NewLine;if (x is System.Collections.IEnumerable obj and not string){var firstLine = true;foreach (var item in obj){if (!firstLine) sw.Write(separator);firstLine = false;sw.Write(item);}}else sw.Write(x);sw.WriteLine();}#pragma warning restore IDE0051}