Submission #66759442

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Reflection;
using System.Security.Cryptography.X509Certificates;
using System.Text;
namespace x
{
    internal class Program
    {
        private static void Main()
        {
            //Eratosthenes era = new Eratosthenes(0);//素数探索の上限値に書き換えること
            Utils utils = new Utils();
            Scanner scanner = new Scanner();
            int n = scanner.Next<int>();
            int m = scanner.Next<int>();
            List<List<(int, long)>> al = new();
            for (int i = 0; i < n; i++)
            {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Reflection;
using System.Security.Cryptography.X509Certificates;
using System.Text;

namespace x
{
    internal class Program
    {
        private static void Main()
        {
            //Eratosthenes era = new Eratosthenes(0);//素数探索の上限値に書き換えること
            Utils utils = new Utils();
            Scanner scanner = new Scanner();

            int n = scanner.Next<int>();
            int m = scanner.Next<int>();
            List<List<(int, long)>> al = new();
            for (int i = 0; i < n; i++)
            {
                al.Add(new());
            }
            for (int i = 0; i < m; i++)
            {
                int a = scanner.Next<int>();
                int b = scanner.Next<int>();
                long w = scanner.Next<long>();
                al[a - 1].Add((b - 1, w));
            }

            long[] dist = new long[n];
            Array.Fill(dist, -1);
            List<long> basis = new();
            void DFS(int v, long xor)
            {
                dist[v] = xor;
                for (int i = 0; i < al[v].Count; i++)
                {
                    int next = al[v][i].Item1;
                    long weight = al[v][i].Item2;
                    if (dist[next] == -1)
                    {
                        DFS(next, xor ^ weight);
                    }
                    else
                    {
                        long cycle = xor ^ weight ^ dist[next];
                        if (cycle != 0)
                        {
                            for (int j = 0; j < basis.Count; j++)
                            {
                                cycle = Math.Min(cycle, cycle ^ basis[j]);
                            }
                            if (cycle != 0)
                            {
                                basis.Add(cycle);
                            }
                        }
                    }
                }
            }

            DFS(0, 0);
            long ans = dist[n - 1];
            for (int i = 0; i < basis.Count; i++)
            {
                ans = Math.Min(ans, ans ^ basis[i]);
            }
            if (ans < 0)
            {
                Console.WriteLine(-1);
            }
            else
            {
                Console.WriteLine(ans);
            }
        }
    }

    public static class DFS
    {
        private static void Run(int current)
        {
        }
    }

    //数値型の範囲
    //int    【10^10】-2,147,483,648 ～ 2,147,483,647
    //long   【10^19】-9,223,372,036,854,775,808 ～ 9,223,372,036,854,775,807
    //double 【10^308】【有効桁数15-17】
    //decimal【10^28】 【有効桁数28-29】

    public class BinarySearchSolver<T>
    {
        private static List<T> list;
        private static T goal;

        public BinarySearchSolver(List<T> list, T goal)
        {
            BinarySearchSolver<T>.list = list;
            BinarySearchSolver<T>.goal = goal;
        }

        public static bool Solve(long mid)
        {
            /*
            long sum = 0;
            for (int i = 0; i < list.Count; i++)
            {
            }
            */

            //midが条件を満たしている場合
            return true;
            //midが条件を満たしていない場合
            //return false;
        }
    }

    internal class UnionFind
    {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n)
        {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++)
            {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int Find(int x)
        {
            if (parent[x] == x)
            {
                return x;
            }
            else
            {
                return parent[x] = Find(parent[x]);
            }
        }

        public void Unite(int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if (x == y) return;

            if (rank[x] < rank[y])
            {
                parent[x] = y;
            }
            else
            {
                parent[y] = x;
                if (rank[x] == rank[y]) rank[x]++;
            }
        }

        public bool Same(int x, int y)
        {
            return Find(x) == Find(y);
        }
    }

    internal class Graph
    {
        private static Stack<int> history = new Stack<int>();
        private static bool[] seen;
        private static bool[] finished;
        private static List<List<int>> graph;
        private static bool isDirected;
        public static bool isCycle = false;
        public static List<int> edgeInCycle = new();
        private static int[] order;
        private static int[] lowLink;
        private static List<(int, int)> bridge = new();
        private static bool[] isArticulation;

        public Graph(List<List<int>> graph, bool isDirected)
        {
            Graph.graph = graph;
            seen = new bool[graph.Count];
            finished = new bool[graph.Count];
            order = new int[graph.Count];
            Array.Fill(order, -1);
            lowLink = new int[graph.Count];
            isArticulation = new bool[graph.Count];
            Graph.isDirected = isDirected;
        }

        public static void CycleDetection(int current, int former)
        {
            seen[current] = true;
            history.Push(current);
            foreach (var next in graph[current])
            {
                if (isCycle) return;
                if (!isDirected && next == former) continue;
                if (finished[next]) continue;
                if (seen[next] && !finished[next])
                {
                    isCycle = true;
                    while (history.Peek() != next)
                    {
                        edgeInCycle.Add(history.Pop());
                    }
                    edgeInCycle.Add(next);
                    edgeInCycle.Reverse();
                    return;
                }

                CycleDetection(next, current);
            }
            finished[current] = true;
            history.Pop();
        }

        public static void LowLinkDFS(int current, int former)
        {
            int childCount = 0;
            foreach (int next in graph[current])
            {
                if (next == former) continue;
                if (order[next] == -1)//未訪問
                {
                    childCount++;
                    LowLinkDFS(next, current);
                    lowLink[current] = Math.Min(lowLink[current], lowLink[next]);

                    if (order[current] < lowLink[next])
                    {
                        bridge.Add((current, next));
                    }

                    if (former != -1 && order[current] <= lowLink[next])
                    {
                        isArticulation[current] = true;
                    }
                }
                else
                {
                    lowLink[current] = Math.Min(lowLink[current], order[next]);
                }
            }
            if (former == -1 && childCount > 1)
            {
                isArticulation[current] = true;
            }
        }

        public List<int> GetArticulationPoints()
        {
            List<int> result = new();
            for (int i = 0; i < isArticulation.Length; i++)
            {
                if (isArticulation[i])
                {
                    result.Add(i);
                }
            }
            return result;
        }

        public List<(int, int)> GetBridges()
        {
            return bridge;
        }
    }

    //よく使うコード
    internal class Utils
    {
        /// <summary>
        /// 与えられた区間が重なっているかどうかを判定する
        /// </summary>
        public bool IsIntersected<T>(T l1, T r1, T l2, T r2) where T : IComparable<T>
        {
            return l1.CompareTo(r2) < 0 && l2.CompareTo(r1) < 0;
        }

        /// <summary>
        /// 繰り返し二乗法（繰り返し自乗法）　x^n % modを計算する
        /// </summary>
        /// <param name="x"></param>
        /// <param name="n"></param>
        /// <param name="mod"></param>
        /// <returns></returns>
        public long ModPow(long x, long n, long mod)
        {
            long res = 1;
            while (n > 0)
            {
                if ((n & 1) == 1)
                {
                    res = res * x % mod;
                }
                x = x * x % mod;
                n >>= 1;
            }
            return res;
        }

        /// <summary>
        /// 文字列から特定の文字を削除する
        /// </summary>
        /// <param name="objective"></param>
        /// <param name="letter"></param>
        /// <returns></returns>
        public string DeleteSpecificLetter(string objective, string letter)
        {
            return objective.Replace(letter, "");
        }

        /// <summary>
        /// 引数で与えられた文字列について，順列を列挙するListを返す
        /// </summary>
        /// <param name="elements">string型の数字も受付可能</param>
        /// <returns></returns>
        public List<string> MakePermutation(string elements)
        {
            if (elements.Length == 1)
            {
                return new List<string>() { elements };
            }

            List<string> result = new List<string>();

            for (int i = 0; i < elements.Length; i++)
            {
                foreach (string s in MakePermutation(elements.Remove(i, 1)))
                {
                    result.Add(elements[i] + s);
                }
            }
            return result;
        }

        /// <summary>
        /// 引数で与えられた文字列について，組み合わせを列挙するListを返す
        /// </summary>
        /// <param name="elementsList">string型の数字も受付可能，重複不可</param>
        /// <param name="nCharas">選ぶ文字数</param>
        /// <param name="allowDuplicates">true:同じ文字を複数回使ってもよい</param>
        /// <returns></returns>
        public List<List<string>> MakeCombinationWithMultiChars(List<string> elementsList, int nCharas, bool allowDuplicates)
        {
            List<List<string>> result = new List<List<string>>();
            MakeCombinationWithMultiCharsHelper(elementsList, nCharas, 0, new List<string>(), result, allowDuplicates);
            return result;
        }

        private void MakeCombinationWithMultiCharsHelper(List<string> elementsList, int nCharas, int startIndex, List<string> currentCombination, List<List<string>> result, bool allowDuplicates)
        {
            if (nCharas == 0)
            {
                result.Add(new List<string>(currentCombination));
                return;
            }

            for (int i = startIndex; i < elementsList.Count; i++)
            {
                currentCombination.Add(elementsList[i]);
                MakeCombinationWithMultiCharsHelper(elementsList, nCharas - 1, allowDuplicates ? i : i + 1, currentCombination, result, allowDuplicates);
                currentCombination.RemoveAt(currentCombination.Count - 1); // 要素を元に戻す
            }
        }

        /// <summary>
        /// (List[i],i)のタプルリストを返す
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <returns></returns>
        public List<(T, int)> MakeTupleWithOrder<T>(List<T> list)
        {
            List<(T, int)> result = new List<(T, int)>();
            for (int i = 0; i < list.Count; i++)
            {
                result.Add((list[i], i));
            }
            return result;
        }

        public string DictionaryOrder(string str)
        {
            return string.Concat(str.OrderBy(ch => ch));
        }

        /// <summary>
        /// リスト内の要素を用いて行列をソートするメソッド
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="matrix"></param>
        /// <param name="ascending">True:昇順 False:降順</param>
        /// <returns></returns>
        public List<List<T>> SortMatrix<T>(List<List<T>> matrix, bool ascending) where T : IComparable
        {
            matrix.Sort((a, b) =>
            {
                for (int i = 0; i < Math.Min(a.Count, b.Count); i++)
                {
                    int comparison = a[i].CompareTo(b[i]);
                    if (comparison != 0)
                    {
                        return ascending ? comparison : -comparison;
                    }
                }
                return ascending ? a.Count.CompareTo(b.Count) : -a.Count.CompareTo(b.Count);
            });
            return matrix;
        }

        /// <summary>
        /// 累積和のリストを返す
        /// </summary>
        /// <param name="list">対象のリスト</param>
        /// <param name="initialValue">初期値，デフォルト=0</param>
        /// <returns></returns>
        public List<int> CumulativeSumList(List<int> list, int initialValue = 0)
        {
            List<int> result = new List<int> { initialValue };
            int sum = initialValue;

            foreach (int item in list)
            {
                sum += item;
                result.Add(sum);
            }

            return result;
        }

        public List<long> CumulativeSumList(List<long> list, long initialValue = 0)
        {
            List<long> result = new List<long> { initialValue };
            long sum = initialValue;

            foreach (long item in list)
            {
                sum += item;
                result.Add(sum);
            }

            return result;
        }

        public List<double> CumulativeSumList(List<double> list, double initialValue = 0)
        {
            List<double> result = new List<double> { initialValue };
            double sum = initialValue;

            foreach (double item in list)
            {
                sum += item;
                result.Add(sum);
            }

            return result;
        }

        /// <summary>
        /// 文字列 str 中で times 回目に key が出現するときのインデックスを返す
        /// </summary>
        /// <param name="str"></param>
        /// <param name="key"></param>
        /// <param name="times"></param>
        /// <returns></returns>
        public static int IndexOfTimes(string str, string key, int times)
        {
            var index = -1;
            for (int i = 0; i < times; i++)
            {
                if ((index = str.IndexOf(key, index + 1)) < 0) break;
            }
            return index;
        }

        public static int IndexOfTimes(List<int> list, int key, int times)
        {
            var index = -1;
            for (int i = 0; i < times; i++)
            {
                if ((index = list.IndexOf(key, index + 1)) < 0) break;
            }
            return index;
        }

        public static List<int> FindDuplication(List<int> list)
        {
            return list.GroupBy(x => x)
                        .Where(g => g.Count() > 1)
                        .Select(x => x.Key)
                        .ToList();
        }

        /// <summary>
        /// 最大公約数を返す
        /// </summary>
        /// <param name="a">bigger one</param>
        /// <param name="b">smaller one</param>
        /// <returns></returns>
        public static long GCD(long a, long b)
        {
            if (b == 0)
            {
                return a;
            }
            return GCD(b, a % b);
        }

        /// <summary>
        /// 最小公倍数を返す
        /// </summary>
        /// <param name="a">bigger one</param>
        /// <param name="b">smaller one</param>
        /// <returns></returns>
        public static long LCM(long a, long b)
        {
            return a / GCD(a, b) * b;
        }

        /// <summary>
        /// 二分探索　半区間で正解の範囲を管理する
        /// 参考：https://twitter.com/meguru_comp/status/697008509376835584
        /// </summary>
        /// <param name="ok">解が存在する値・インデックス</param>
        /// <param name="ng">解が存在しない値・インデックス</param>
        /// <param name="list">探索対象のリスト</param>
        /// <param name="goal">目的の値・しきい値</param>
        public static long BinarySearch<T>(long ok, long ng, List<T> list, T goal)
        {
            while (Math.Abs(ok - ng) > 1)
            {
                long mid = (ok + ng) / 2;
                //コンストラクタで初期化を行う
                BinarySearchSolver<T> bs = new BinarySearchSolver<T>(list, goal);
                if (BinarySearchSolver<T>.Solve(mid))
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }
            return ok;
        }

        /// <summary>
        /// itemよりも大きな値の最小のインデックスを返す<br/>
        /// Tips：「itemよりも小さな最大」→「item-1よりも大きな値の最小 -1」
        /// </summary>
        public static int UpperBound<T>(List<T> list, T item) where T : IComparable<T>
        {
            return ~list.BinarySearch(item, new UpperBound<T>());
        }

        /// <summary>
        /// item以上の最小のインデックスを返す
        /// </summary>
        public static int LowerBound<T>(List<T> list, T item) where T : IComparable<T>
        {
            return ~list.BinarySearch(item, new LowerBound<T>());
        }
    }

    public class UpperBound<T> : IComparer<T> where T : IComparable<T>
    {
        public int Compare(T x, T y)
        {
            return 0 < x.CompareTo(y) ? 1 : -1;
        }
    }

    public class LowerBound<T> : IComparer<T> where T : IComparable<T>
    {
        public int Compare(T x, T y)
        {
            return 0 <= x.CompareTo(y) ? 1 : -1;
        }
    }
}

public class Eratosthenes
{
    private bool[] isPrime;
    private int[] minFactor;

    public Eratosthenes(int max)
    {
        isPrime = new bool[max + 1];
        minFactor = Enumerable.Repeat(-1, max + 1).ToArray();
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        minFactor[1] = 1;

        for (int i = 2; i <= max; i++)
        {
            if (isPrime[i])
            {
                minFactor[i] = i;
                for (int j = 2 * i; j <= max; j += i)
                {
                    isPrime[j] = false;
                    if (minFactor[j] == -1) minFactor[j] = i;
                }
            }
        }
    }

    /// <summary>
    /// 指定した整数を素因数分解し，（素因数,指数）のリストを返す
    /// </summary>
    /// <param name="n">素因数分解の対象</param>
    /// <returns>（素因数,指数）</returns>
    public List<(int prime, int exponent)> Factorize(int n)
    {
        List<(int prime, int exponent)> res = new List<(int prime, int exponent)>();
        while (n > 1)
        {
            int p = minFactor[n];
            int exp = 0;
            while (minFactor[n] == p)
            {
                n /= p;
                exp++;
            }
            res.Add((p, exp));
        }
        return res;
    }

    /// <summary>
    /// 指定した整数の約数を列挙する
    /// </summary>
    /// <param name="n">約数列挙の対象</param>
    /// <returns>約数のリスト</returns>
    public List<int> Divisors(int n)
    {
        List<(int prime, int exponent)> factors = Factorize(n);
        List<int> res = new();
        res.Add(1);

        foreach (var (prime, exponent) in factors)
        {
            int resSize = res.Count;
            for (int i = 0; i < resSize; i++)
            {
                int v = 1;
                for (int j = 0; j < exponent; j++)
                {
                    v *= prime;
                    res.Add(res[i] * v);
                }
            }
        }
        return res;
    }
}

internal class Scanner
{
    private string[] s;
    private int i;
    private char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    private string NextString()
    {
        if (i < s.Length) return s[i++];
        string st;
        do
        {
            st = Console.ReadLine();
        } while (string.IsNullOrWhiteSpace(st));

        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s.Length > 0 ? s[i++] : NextString();
    }

    public T Next<T>()
    {
        return (T)Convert.ChangeType(NextString(), typeof(T));
    }

    public T[] Array<T>()
    {
        return Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries)
                                 .Select(x => (T)Convert.ChangeType(x, typeof(T)))
                                 .ToArray();
    }

    public List<T> InputList<T>()
    {
        return Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries)
                                 .Select(x => (T)Convert.ChangeType(x, typeof(T)))
                                 .ToList();
    }
}

public class Output
{
    public static void Matrix<T>(List<List<T>> matrix)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < matrix.Count; i++)
        {
            for (int j = 0; j < matrix[i].Count; j++)
            {
                sb.Append(matrix[i][j]);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

public static class IEnumerableExtensions
{
    public static IEnumerable<TAccumulate> Scan<TSource, TAccumulate>(
        this IEnumerable<TSource> source,
        Func<TAccumulate, TSource, TAccumulate> func,
        TAccumulate seed)
    {
        TAccumulate accumulator = seed;
        foreach (var item in source)
        {
            accumulator = func(accumulator, item);
            yield return accumulator;
        }
    }
}

Submission Info

Judge Result