結果
| 問題 | No.1737 One to N |
| ユーザー |
 TAKA 00
|
| 提出日時 | 2022-12-12 17:41:55 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 63 ms / 2,000 ms |
| コード長 | 41,089 bytes |
| コンパイル時間 | 15,684 ms |
| コンパイル使用メモリ | 166,416 KB |
| 実行使用メモリ | 193,964 KB |
| 最終ジャッジ日時 | 2024-11-06 15:58:57 |
| 合計ジャッジ時間 | 18,910 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(83,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(150,20): warning CS8981: 型名 'mod' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(174,20): warning CS8981: 型名 'toolbox' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1101,27): warning CS0162: 到達できないコードが検出されました [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1111,17): warning CS0219: 変数 'k' は割り当てられていますが、その値は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(29,31): warning CS0169: フィールド 'Program.Warshall_Floyd' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(26,20): warning CS0169: フィールド 'Program.BFS' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(32,19): warning CS0169: フィールド 'Program.FF' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(34,20): warning CS0169: フィールド 'Program.RMQ' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(2
ソースコード
using System;using System.Collections.Generic;using System.Linq;using System.Numerics;namespace test{internal class Program{static void Main(string[] args){cin = new input();mod = new mod(1000000007);toolbox = new toolbox();Priority_Queue = new Priority_Queue(false);var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(sw);int n = cin.intreed();Console.WriteLine(toolbox.prime_factorize(n).Sum());Console.Out.Flush();}static input cin;static mod mod;static toolbox toolbox;static UnionFind UnionFind;static BFS BFS;static DFS DFS;static Priority_Queue Priority_Queue;static Warshall_Floyd Warshall_Floyd;static SPFA SPFA;static Kruskal Kruskal;static FF FF;static TSP TSP;static RMQ RMQ;}public static class Extensions{public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key){if (dic.ContainsKey(key))dic[key]++;elsedic.Add(key, 1);return dic;}public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value){if (dic.ContainsKey(key))dic[key].Add(value);elsedic.Add(key, new List<T2>() { value });return dic;}public static T list_pop_back<T>(this List<T> a){var k = a[a.Count - 1];a.RemoveAt(a.Count - 1);return k;}public static T chmin<T>(ref this T a, T b)where T : struct, IComparable{if (a.CompareTo(b) > 0)return a = b;elsereturn a;}public static T chmax<T>(ref this T a, T b)where T : struct, IComparable{if (a.CompareTo(b) < 0)return a = b;elsereturn a;}}internal class input{string[] soloinput;int t;public input(){soloinput = new string[0];t = 0;}public string soloreed(){if (t < soloinput.Length){return soloinput[t++];}string input = Console.ReadLine();while (input == ""){input = Console.ReadLine();}soloinput = input.Split(" ");t = 0;return soloinput[t++];}public int intreed(){return int.Parse(soloreed());}public int[] arrayint(int N){int[] A = new int[N];for (int i = 0; i < N; i++){A[i] = intreed();}return A;}public long longreed(){return long.Parse(soloreed());}public long[] arraylong(long N){long[] A = new long[N];for (long i = 0; i < N; i++){A[i] = longreed();}return A;}public decimal decimalreed(){return decimal.Parse(soloreed());}public decimal[] arraydecimal(long N){decimal[] A = new decimal[N];for (decimal i = 0; i < N; i++){A[(long)i] = decimalreed();}return A;}}internal class mod{public long T { get; set; }public mod(long mod = 1000000007){T = mod;}public long addition(long A, long B){decimal C = A + B;return (long)C % T;}public long subtraction(long A, long B){decimal C = A - B;return C % T >= 0 ? (long)C % T : (long)(C + T) % T;}public long multiplication(long A, long B){return ((A % T) * (B % T)) % T;}}internal class toolbox{string Y = "Yes";string N = "No";static input cin;public toolbox(){cin = new input();}public long[] CumulativeSum(long[] A, bool mode = true){if (mode == false) Array.Reverse(A);long[] back = new long[A.Length + 1];back[0] = 0;for (int i = 1; i <= A.Length; i++){back[i] = back[i - 1] + A[i - 1];}if (mode == false) Array.Reverse(A);return back;}public long[] Eratosthenes(long A){A++;var back = new List<long>();bool[] ch = new bool[A];for (int i = 2; i < A; i++) ch[i] = true;for (long i = 2; i < Math.Sqrt(A); i++){if (ch[i] == true){back.Add(i);for (long t = 1; i * t < A; t++){ch[i * t] = false;}}}for (long i = 0; i < A; i++){if (ch[i] == true) back.Add(i);}return back.Distinct().ToArray();}public void Swap<T>(ref T a, ref T b){var i = a;a = b;b = i;}public void LSwap<T>(ref List<T> A, int a, int b){var i = A[a];A[a] = A[b];A[b] = i;}public long Gcd(long A, long B){while (A != 0){B %= A;Swap(ref A, ref B);}return B;}public long[] AllDivisors(long N){var back = new List<long>();for (int i = 1; Math.Pow(i, 2) <= N; i++){if (N % i == 0){back.Add(i);back.Add(N / i);}}return back.Distinct().ToArray();}public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata){if (indata.Count() == 1) yield return new T[] { indata.First() };foreach (var i in indata){var used = new T[] { i };var unused = indata.Except(used);foreach (var t in ExhaustiveEnumeration(unused))yield return used.Concat(t).ToArray();}//How to use//var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));}public bool[,] bitallsearch(int N){bool[,] back = new bool[(int)Math.Pow(2, N), N];for (int i = 0; i < Math.Pow(2, N); i++){for (int t = 0; t < N; t++){var k = (i >> t) & 1;if (k == 1){back[i, t] = true;}}}return back;}public static int BS<T>(T[] A, T key)where T : IComparable{//このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)int left = 0;int right = A.Length;int mid = 0;while (left < right){mid = (left + right) / 2;if (A[mid].CompareTo(key) == 0)return mid;else if (A[mid].CompareTo(key) > 0)right = mid;else if (A[mid].CompareTo(key) < 0)left = mid + 1;}return -1;}public static int lower_bound<T>(T[] a, T v){return lower_bound(a, v, Comparer<T>.Default);}public static int lower_bound<T>(T[] A, T key, Comparer<T> v){int left = 0;int right = A.Length - 1;int mid = 0;var W = 0;while (left <= right){mid = (left + right) / 2;W = v.Compare(A[mid], key);if (W == -1)left = mid + 1;elseright = mid - 1;}return left;}public long[] prime_factorize(long N){long T = N;var back = new List<long>();for (long i = 2; i * i <= T; i++){if (T % i != 0) continue;while (T % i == 0){back.Add(i);T /= i;}}if (T != 1) back.Add(T);return back.ToArray();}public long[] One_dimensional_Coordinate_Compression(long[] A){long[] back = new long[A.Length];var T = A.Distinct().ToList();T.Sort();for (int i = 0; i < A.Length; i++)back[i] = T.BinarySearch(A[i]);return back;}public void setYN(string A = "Yes", string B = "No"){Y = A;N = B;}public void YN(bool ans){if (ans)Console.WriteLine(Y);elseConsole.WriteLine(N);}public string[] x_dekakou(int H, int W){var s = new string[H + 2];for (int i = 0; i < W + 2; i++){s[0] += "x";s[H + 1] += "x";}for (int i = 1; i < H + 1; i++){//x場外 .白 #黒s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";}return s;}public List<List<string>> x_dekakou_string(int H, int W){var back = new List<List<string>>();for (int i = 0; i < H + 2; i++)back.Add(Enumerable.Repeat<string>("", W + 2).ToList());for (int i = 0; i < W + 2; i++){back[0][i] = "x";back[H + 1][i] = "x";}for (int i = 1; i <= H; i++){back[i][0] = "x";back[i][W + 1] = "x";for (int t = 1; t <= W; t++)back[i][t] = cin.soloreed();}return back;}}internal class UnionFind{public int[] tree { get; private set; }static toolbox toolbox;public UnionFind(int s){tree = Enumerable.Repeat<int>(-1, s + 1).ToArray();}public int getroot(int i){return tree[i] < 0 ? i : tree[i] = getroot(tree[i]);}public bool groupcheck(int i, int t){return getroot(i) == getroot(t);}public bool unite(int i, int t){toolbox = new toolbox();var x = getroot(i);var y = getroot(t);if (x != y){if (tree[x] > tree[y]){toolbox.Swap(ref x, ref y);}tree[x] += tree[y];tree[y] = x;}return x != y;}public int get_cnt(int i){return tree[getroot(i)] * -1;}}internal class BFS{//この関数は基本的に1_indexで処理されるpublic int[] dist { get; set; }public bool interactive { get; set; }private Queue<int> que = new Queue<int>();private List<List<int>> Graph = new List<List<int>>();public BFS(int i, bool cnt = true){Set_BFS(i, cnt);}public void Set_BFS(int i, bool cnt = true){//(頂点数、双方向グラフであるT/F)dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();interactive = cnt;for (int t = 0; t <= i; t++){Graph.Add(new List<int>());}}public void Connect_Graph(int i, int t){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph[i].Add(t);if (interactive)Graph[t].Add(i);}public void Start_BFS(int i){//(捜索を始める頂点(int))dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();que.Enqueue(i);dist[i] = 0;while (que.Count != 0){var t = que.Dequeue();for (int w = 0; w < Graph[t].Count; w++){if (dist[Graph[t][w]] == -1){que.Enqueue(Graph[t][w]);dist[Graph[t][w]] = dist[t] + 1;}}}}public void Start_BFS(List<int> i){dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();foreach (var t in i){que.Enqueue(t);dist[t] = 0;}while (que.Count != 0){var t = que.Dequeue();for (int w = 0; w < Graph[t].Count; w++){if (dist[Graph[t][w]] == -1){que.Enqueue(Graph[t][w]);dist[Graph[t][w]] = dist[t] + 1;}}}}}internal class DFS{//この関数は基本的に1_indexで処理されるprivate int[] dist;private bool interactive = true;private Stack<int> stc = new Stack<int>();private List<List<int>> Graph = new List<List<int>>();public DFS(){}public void Set_DFS(int i, bool cnt = true){//(頂点数、双方向グラフであるT/F)dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();interactive = cnt;for (int t = 0; t <= i; t++){Graph.Add(new List<int>());}}public void Connect_Graph(int i, int t){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph[i].Add(t);if (interactive)Graph[t].Add(i);}public void Start_DFS(int i, bool cnt = false){//(捜索を始める頂点(int))stc.Push(i);dist[i] = 0;while (stc.Count != 0){var t = stc.Pop();for (int w = 0; w < Graph[t].Count; w++){if (dist[Graph[t][w]] == -1){stc.Push(Graph[t][w]);}}}}public int Get_Cost(int i){return dist[i];}}internal class Dijkstra{static Priority_Queue Priority_Queue;public long[] dist { get; set; }public bool interactive { get; set; }public int[] prev { get; set; }/// <summary>/// 行先,コスト/// </summary>public List<List<(long, long)>> Graph { get; set; }public Dijkstra(int n, bool cnt = true){Priority_Queue = new Priority_Queue(false);dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();Graph = new List<List<(long, long)>>();prev = Enumerable.Repeat<int>(-1, n + 1).ToArray();//前の頂点を保管するfor (int i = 0; i <= n; i++){Graph.Add(new List<(long, long)>());}interactive = cnt;}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph[i].Add((t, cost));if (interactive)Graph[t].Add((i, cost));}public void Start_Dijkstra(long i){dist[i] = 0;Priority_Queue.Enqueue(0, i);while (Priority_Queue.Queue.Count != 0){var t = Priority_Queue.Dequeue();int v = (int)t.Item2;if (dist[v] < t.Item1)continue;for (int w = 0; w < Graph[v].Count; w++){var e = Graph[v][w];if (dist[(int)e.Item1] <= dist[v] + e.Item2)continue;else{dist[(int)e.Item1] = dist[v] + e.Item2;Priority_Queue.Enqueue(dist[(int)e.Item1], e.Item1);prev[e.Item1] = v;}}}}public List<(int, int)> Get_tree(){var back = new List<(int, int)>();for (int i = 1; i <= dist.Length - 1; i++){back.Add((i, prev[i]));}return back;}}internal class Priority_Queue{toolbox toolbox = new toolbox();public List<(long, long)> Queue { get; private set; }/// <summary>/// true==>大きいやつから出るよ false==>小さいやつからでるよ/// </summary>public bool revase { get; set; }public Priority_Queue(bool cnt = true){Queue = new List<(long, long)>();revase = cnt;}public void Enqueue(long a, long b){if (revase == false)a *= -1;int i = Queue.Count, t;Queue.Add((a, b));while (i != 0){t = (i - 1) / 2;if (Queue[i].Item1 > Queue[t].Item1){var k = Queue[i];Queue[i] = Queue[t];Queue[t] = k;i = t;}else{break;}}}public (long, long) Dequeue(){int a = Queue.Count - 1;var back = Queue[0];Queue[0] = Queue[a];Queue.RemoveAt(a);for (int i = 0, j; (j = 2 * i + 1) < a;){if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)j++;if (Queue[i].Item1 < Queue[j].Item1){var k = Queue[i];Queue[i] = Queue[j];Queue[j] = k;i = j;}else{break;}}if (revase == false)back.Item1 *= -1;return back;}}internal class Generic_Priority_Queue<T>{toolbox toolbox = new toolbox();public List<(long, T)> Queue { get; private set; }/// <summary>/// true==>大きいやつから出るよ false==>小さいやつからでるよ/// </summary>public bool revase { get; set; }public Generic_Priority_Queue(bool cnt = true){Queue = new List<(long, T)>();revase = cnt;}public void Enqueue(long a, T b){if (revase == false)a *= -1;int i = Queue.Count, t;Queue.Add((a, b));while (i != 0){t = (i - 1) / 2;if (Queue[i].Item1 > Queue[t].Item1){var k = Queue[i];Queue[i] = Queue[t];Queue[t] = k;i = t;}else{break;}}}public (long, T) Dequeue(){int a = Queue.Count - 1;var back = Queue[0];Queue[0] = Queue[a];Queue.RemoveAt(a);for (int i = 0, j; (j = 2 * i + 1) < a;){if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)j++;if (Queue[i].Item1 < Queue[j].Item1){var k = Queue[i];Queue[i] = Queue[j];Queue[j] = k;i = j;}else{break;}}if (revase == false)back.Item1 *= -1;return back;}public (long, T) get_first(){if (Queue.Count == 0)return (default(long), default(T));elsereturn Queue[0];}}internal class SPFA{private Queue<long> que;public long[] dist { get; set; }public bool interactive { get; set; }public List<List<(long, long)>> Graph { get; set; }public List<long> times { get; set; }public List<bool> pending { get; set; }public SPFA(int n, bool cnt = true){que = new Queue<long>();dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();times = Enumerable.Repeat<long>(0, n + 1).ToList();pending = Enumerable.Repeat<bool>(false, n + 1).ToList();Graph = new List<List<(long, long)>>();for (int i = 0; i <= n; i++){Graph.Add(new List<(long, long)>());}interactive = cnt;BFS = new BFS(n, false);}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph[i].Add((t, cost));if (interactive)Graph[t].Add((i, cost));BFS.Connect_Graph(i, t);}public bool Start_SPFA(int i){//(捜索を始める頂点(int))que.Enqueue(i);pending[i] = true;dist[i] = 0;times[i]++;while (que.Count != 0){var t = (int)que.Dequeue();pending[t] = false;for (int w = 0; w < Graph[t].Count; w++){long cost_before = dist[t] + Graph[t][w].Item2;if (dist[Graph[t][w].Item1] <= cost_before)continue;dist[Graph[t][w].Item1] = cost_before;if (!pending[(int)Graph[t][w].Item1]){if (times[(int)Graph[t][w].Item1]++ >= Graph.Count){BFS.Start_BFS((int)Graph[t][w].Item1);if (BFS.dist[times.Count - 1] != -1)return false;elsecontinue;}que.Enqueue(Graph[t][w].Item1);pending[(int)Graph[t][w].Item1] = true;}}}return true;}static BFS BFS;}internal class Bellman_Ford{public long[] dist { get; set; }public bool interactive { get; set; }/// <summary>/// 移動元,移動先,コスト/// </summary>public List<(long, long, long)> Graph { get; set; }public int v;public Bellman_Ford(int n, bool cnt = true){v = n;//ここの初期値(long.MaxValue/40)注意 オーバーフローしそうdist = Enumerable.Repeat<long>(long.MaxValue / 40, n + 1).ToArray();Graph = new List<(long, long, long)>();interactive = cnt;}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph.Add((i, t, cost));if (interactive)Graph.Add((t, i, cost));}public bool Start_Bellman_Ford(int i){dist[i] = 0;int cnt = 0;while (cnt < v){bool end = true;foreach (var t in Graph){if (t.Item1 != long.MaxValue && dist[t.Item1] + t.Item3 < dist[t.Item2]){dist[t.Item2] = dist[t.Item1] + t.Item3;end = false;}}if (end)break;cnt++;}return (cnt == v);}}internal class Warshall_Floyd{public long[,] dist { get; private set; }public bool interactive { get; set; }public int v;public Warshall_Floyd(int n, bool cnt = true){dist = new long[n + 1, n + 1];for (int i = 0; i <= n; i++)for (int t = 0; t <= n; t++){if (i == t){dist[i, t] = 0;}else{dist[i, t] = long.MaxValue / 40;}}interactive = cnt;v = n;}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)dist[i, t] = cost;if (interactive)dist[t, i] = cost;}public void Start_Warshall_Floyd(){for (int i = 1; i <= v; i++)for (int t = 1; t <= v; t++)for (int w = 1; w <= v; w++)dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);//dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);}}internal class Binary_Trie{Node tree;const int SZ = 64;//const int SZ = 12;int ans = 0;List<byte> ans_byte;public Binary_Trie(){tree = new Node();ans_byte = new List<byte>();}public void add(long i){tree = add_fx(tree, i);}private Node add_fx(Node now, long x, int now_height = SZ - 1){if (now == null)now = new Node();now.cnt++;if (now_height == -1)return now;long ne = x >> now_height & 1;now[(int)ne] = add_fx(now[(int)ne], x, now_height - 1);return now;}public void delete(long i){tree = delete_fx(tree, i);}private Node delete_fx(Node now, long x, int now_height = SZ - 1){if (now == null)return now;if (now.cnt == 0)return now;elsenow.cnt--;if (now_height == -1)return now;long ne = x >> now_height & 1;now[(int)ne] = delete_fx(now[(int)ne], x, now_height - 1);return now;}public int search(long i){ans = 0;search_fx(tree, i);return ans;}private Node search_fx(Node now, long x, int now_height = SZ - 1){if (now == null){ans = 0;return now;}else{if (now_height == -1)return now;long ne = x >> now_height & 1;ans = now.cnt;now[(int)ne] = search_fx(now[(int)ne], x, now_height - 1);return now;}}public int get_min_cnt(long i){ans = 0;get_min_cnt_fx(tree, i);return ans;}private Node get_min_cnt_fx(Node now, long x, int now_height = SZ - 1){if (now == null)return now;else{if (now_height == -1){ans += now.cnt;return now;}long ne = x >> now_height & 1;if (ne == 1 && now[0] != null)ans += now[0].cnt;now[(int)ne] = get_min_cnt_fx(now[(int)ne], x, now_height - 1);return now;}}public int get_max_cnt(long i){ans = 0;get_max_cnt_fx(tree, i);return ans;}private Node get_max_cnt_fx(Node now, long x, int now_height = SZ - 1){if (now == null)return now;else{if (now_height == -1){ans += now.cnt;return now;}long ne = x >> now_height & 1;if (ne == 0 && now[1] != null)ans += now[1].cnt;now[(int)ne] = get_max_cnt_fx(now[(int)ne], x, now_height - 1);return now;}}public long get_min(int xor = 0){return get_min_fx(tree, xor);}private long get_min_fx(Node now, int xor, int now_height = SZ - 1){if (SZ == -1) return 0;int ne = xor >> SZ & 1;if (now[ne] == null || now[ne].cnt == 0){}return 1;}public void ch(){int k = 0;}public class Node{public int cnt { get; set; }public Node[] node = new Node[2];public Node(){cnt = 0;node[0] = null;node[1] = null;}public Node this[int i]{get { return this.node[i]; }set { this.node[i] = value; }}public void make_node(int i){node[i] = new Node();}}}public class Kruskal{public List<(long, int, int)> Graph { get; set; }//コスト 行先、行先static UnionFind UnionFind;public Kruskal(int n){Graph = new List<(long, int, int)>();UnionFind = new UnionFind(n);}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる)Graph.Add((cost, i, t));}public List<(long, int, int)> start_Kruskal(){var back = new List<(long, int, int)>();Graph = Graph.OrderBy(i => i.Item1).ToList();foreach (var i in Graph){if (!UnionFind.groupcheck(i.Item2, i.Item3)){UnionFind.unite(i.Item2, i.Item3);back.Add(i);}}return back;}public bool is_conected(int x, int y){return UnionFind.groupcheck(x, y);}}public class FF{public List<List<(int, long, int)>> Graph { get; set; }//行先,コスト,逆辺のインデックスpublic List<bool> flag { get; set; }public int end { get; set; }public FF(int n, int g = -1){if (g == -1)g = n;flag = Enumerable.Repeat<bool>(false, n + 1).ToList();Graph = new List<List<(int, long, int)>>();for (int i = 0; i <= n; i++){Graph.Add(new List<(int, long, int)>());}end = g;}public void Connect_Graph(int i, int t, long cost){//(i==>tの辺を繋げる、気合で逆辺もつなげる)int cnt_sei = Graph[i].Count;//正の辺のインデックスint cnt_gixyaku = Graph[t].Count;//逆辺のインデックスGraph[i].Add((t, cost, cnt_gixyaku));Graph[t].Add((i, 0, cnt_sei));}public int Start_FF(int x, int fl){if (flag[x])return -1;flag[x] = true;if (x == end)return fl;int r = -1;for (int t = 0; t < Graph[x].Count; t++){var hen = Graph[x][t];var w = hen.Item1;//行先var c = hen.Item2;//コストvar i = hen.Item3;//逆辺でのインデックスif (c == 0)continue;r = Start_FF((int)w, (int)Math.Min(fl, c));if (r == -1)continue;else{//容量減らすGraph[x][t] = (w, c - r, i);//逆辺増やすGraph[w][i] = (x, Graph[w][i].Item2 + r, t);return r;}}return -1;}}internal class RMQ{List<long> tree { get; set; }//完全二分木List<long> lazy_list { get; set; }//遅延用Func<long, long, long, (long, long)> lazy_update_fx;//親、子供1,子供2==>(子供１，子供2)//親から子に作用する関数Func<long, long, long> update_fx;//子供1,子供2==>親Func<long, long, long> lazy_fx;//作用先、lazy_list[i]==>作用先int n;long inf_tree = long.MaxValue / 4;long inf_lazy = 0;public RMQ(int i, Func<long, long, long, (long, long)> lazy_update_fx, Func<long, long, long> update_fx, Func<long, long, long> lazy_fx,long inf_tree = long.MaxValue / 4, long inf_lazy = 0){tree = new List<long>();lazy_list = new List<long>();this.inf_lazy = inf_lazy;this.inf_tree = inf_tree;this.lazy_update_fx=lazy_update_fx;this.update_fx = update_fx;this.lazy_fx = lazy_fx;n = 1;while (n <= i)n *= 2;for (int t = 0; t < n * 2; t++){tree.Add(inf_tree);lazy_list.Add(inf_lazy);}}public RMQ(int i, List<long> v, Func<long, long, long, (long, long)> lazy_update_fx, Func<long, long, long> update_fx, Func<long, long, long> lazy_fx, long inf_tree = long.MaxValue / 4, long inf_lazy = 0){tree = new List<long>();lazy_list = new List<long>();this.inf_lazy = inf_lazy;this.inf_tree = inf_tree;this.lazy_update_fx = lazy_update_fx;this.update_fx = update_fx;this.lazy_fx = lazy_fx;n = 1;while (n <= i)n *= 2;for (int t = 0; t < n * 2; t++){tree.Add(inf_tree);lazy_list.Add(inf_lazy);}for(int t=0; t<v.Count; t++)tree[t+n]=v[t];for (int t = n - 2; t >= 0; t--)tree[t] = update_fx(tree[t * 2 + 1], tree[t * 2] + 2);}private void lazy(int i){if (lazy_list[i] == 0)return;if (i < n - 1)(lazy_list[i * 2 + 1], lazy_list[i * 2 + 2]) = lazy_update_fx(lazy_list[i],lazy_list[i * 2 + 1], lazy_list[i * 2 + 2]);tree[i] = lazy_fx(tree[i], lazy_list[i]);lazy_list[i] = 0;}public void update(int l,int r,int value){update(0, value, 0, n, l, r);}public void update(int index,int value){update(0, value, 0, n, index, index+1);}private void update(int index,int value,int now_l,int now_r,int L,int R){lazy(index);if(now_l>=L&&now_r<=R){lazy_list[index] = value;lazy(index);}else if(L<now_r&&now_l<R){update(index * 2 + 1, value, now_l, (now_l + now_r) / 2,L,R);update(index * 2 + 2, value, (now_l+now_r)/2, now_r, L, R);tree[index] = update_fx(tree[index * 2 + 1], tree[index * 2 + 2]);}}public long get(int l,int r){//lは含む rは含まないreturn get(0, 0, n, l, r);}public long get(int index){return tree[n + index - 1];}private long get(int index,int now_l,int now_r,int L,int R){lazy(index);if (now_r<=L||R<=now_l)return inf_tree;else if (now_l>=L&&now_r<=R)return tree[index];else{long vl = get(index * 2 + 1, now_l, (now_l + now_r) / 2, L, R);long vr = get(index * 2 + 2, (now_l + now_r) / 2, now_r, L, R);return update_fx(vl, vr);}}}public class TSP{/// <summary>/// 0indexedです！！！！ 1にしたいけど無理！！！！！！！！！/// 引数も0indexで投げてください/// </summary>public readonly double double_inf = double.MaxValue / 128;const long long_inf = long.MaxValue / 128;public List<List<double>> dp { get; set; }public bool interactive { get; set; }public List<(double x,double y)> Graph { get; set; }public TSP(int n, bool cnt = true){dp = new List<List<double>>();for (int i = 0; i < Math.Pow(2, n); i++){dp.Add(new List<double>(n));for (int t = 0; t < n; t++){dp[i].Add(double_inf);}}Graph = new List<(double x, double y)>();interactive = cnt;}public void Connect_Graph(double x, double y){//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)Graph.Add((x, y));}public void start_tsp(int n){for(int i=0; i<Graph.Count; i++){dp[1 << i][i] = Math.Sqrt(Graph[i].x * Graph[i].x + Graph[i].y * Graph[i].y);}for (int flag = 0; flag < 1 << Graph.Count; flag++){var cnt_get_booster = 1 << BitOperations.PopCount((uint)flag >> n);for (int now = 0; now < Graph.Count; now++){if (dp[flag][now] == double_inf)continue;for (int next = 0; next < Graph.Count; next++){if ((flag & (1 << next)) != 0)continue;dp[flag | (1 << next)][next] = Math.Min(dp[flag | (1 << next)][next],dp[flag][now] + get_cost(now,next)/cnt_get_booster);}}}}public double get_cost(int i,int t){return Math.Sqrt(Math.Pow(2, (Graph[i].x - Graph[t].x) + Math.Pow(2, (Graph[i].y - Graph[t].y))));}}}