Submission #28551552


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

namespace Tasks
{
    public class E
    {
        public static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (N, M, Q) = Scanner.Scan<int, int, int>();
            var E1 = new Edge[M];
            var E2 = new Edge[Q];
            for (var i = 0; i < M; i++)
            {
                var (a, b, c) = Scanner.Scan<int, int, int>();
                a--; b--;
                E1[i] = new Edge(-1, a, b, c);
            }

            for (var i = 0; i < Q; i++)
            {
                var (a, b, c) = Scanner.Scan<int, int, int>();
                a--; b--;
                E2[i] = new Edge(i, a, b, c);
            }

            var answer = new bool[Q];
            var dsu = new DisjointSetUnion(N);
            foreach (var e in E1.Concat(E2).OrderBy(x => x.Cost))
            {
                if (dsu.IsSame(e.U, e.V)) continue;
                if (e.ID == -1)
                {
                    dsu.Merge(e.U, e.V);
                }
                else
                {
                    answer[e.ID] = true;
                }
            }

            Console.WriteLine(string.Join("\n", answer.Select(x => x ? "Yes" : "No")));
        }

        public class Edge
        {
            public int ID { get; }
            public int U { get; }
            public int V { get; }
            public int Cost { get; }
            public Edge(int id, int u, int v, int cost) => (ID, U, V, Cost) = (id, u, v, cost);
        }


        public class DisjointSetUnion
        {
            private readonly int _length;
            private readonly int[] _parentOrSize;
            public DisjointSetUnion(int length = 0)
            {
                if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
                _length = length;
                _parentOrSize = new int[_length];
                Array.Fill(_parentOrSize, -1);
            }
            public int Merge(int u, int v)
            {
                if (u < 0 || _length <= u) throw new ArgumentOutOfRangeException(nameof(u));
                if (v < 0 || _length <= v) throw new ArgumentOutOfRangeException(nameof(v));
                var (x, y) = (LeaderOf(u), LeaderOf(v));
                if (x == y) return x;
                if (-_parentOrSize[x] < -_parentOrSize[y]) (x, y) = (y, x);
                _parentOrSize[x] += _parentOrSize[y];
                _parentOrSize[y] = x;
                return x;
            }
            public bool IsSame(int u, int v)
            {
                if (u < 0 || _length <= u) throw new ArgumentOutOfRangeException(nameof(u));
                if (v < 0 || _length <= v) throw new ArgumentOutOfRangeException(nameof(v));
                return LeaderOf(u) == LeaderOf(v);
            }
            public int LeaderOf(int v)
            {
                if (v < 0 || _length <= v) throw new ArgumentOutOfRangeException(nameof(v));
                if (_parentOrSize[v] < 0) return v;
                return _parentOrSize[v] = LeaderOf(_parentOrSize[v]);
            }
            public int SizeOf(int v)
            {
                if (v < 0 || _length <= v) throw new ArgumentOutOfRangeException(nameof(v));
                return -_parentOrSize[LeaderOf(v)];
            }
            public IEnumerable<IEnumerable<int>> GetGroups()
            {
                var ret = new List<int>[_length].Select(x => new List<int>()).ToArray();
                for (var i = 0; i < _length; i++) ret[LeaderOf(i)].Add(i);
                return ret.Where(x => x.Any());
            }
        }

        public static class Scanner
        {
            public static T Scan<T>() where T : IConvertible => Convert<T>(ScanLine()[0]);
            public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
            {
                var line = ScanLine();
                return (Convert<T1>(line[0]), Convert<T2>(line[1]));
            }
            public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
            {
                var line = ScanLine();
                return (Convert<T1>(line[0]), Convert<T2>(line[1]), Convert<T3>(line[2]));
            }
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
            {
                var line = ScanLine();
                return (Convert<T1>(line[0]), Convert<T2>(line[1]), Convert<T3>(line[2]), Convert<T4>(line[3]));
            }
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
            {
                var line = ScanLine();
                return (Convert<T1>(line[0]), Convert<T2>(line[1]), Convert<T3>(line[2]), Convert<T4>(line[3]), Convert<T5>(line[4]));
            }
            public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
            {
                var line = ScanLine();
                return (Convert<T1>(line[0]), Convert<T2>(line[1]), Convert<T3>(line[2]), Convert<T4>(line[3]), Convert<T5>(line[4]), Convert<T6>(line[5]));
            }
            public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanLine().Select(Convert<T>);
            private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
            private static string[] ScanLine() => Console.ReadLine()?.Trim().Split(' ') ?? Array.Empty<string>();
        }
    }
}

Submission Info

Submission Time
Task E - MST + 1
User AconCavy
Language C# (.NET Core 3.1.201)
Score 500
Code Size 6295 Byte
Status AC
Exec Time 633 ms
Memory 70828 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 13
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_tree_00.txt, 01_tree_01.txt, 01_tree_02.txt, 01_tree_03.txt, 01_tree_04.txt, 02_path_00.txt, 02_path_01.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 04_perfect_00.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 88 ms 28440 KiB
00_sample_01.txt AC 90 ms 28120 KiB
01_tree_00.txt AC 596 ms 70496 KiB
01_tree_01.txt AC 633 ms 70504 KiB
01_tree_02.txt AC 597 ms 70292 KiB
01_tree_03.txt AC 604 ms 70492 KiB
01_tree_04.txt AC 603 ms 70348 KiB
02_path_00.txt AC 577 ms 70828 KiB
02_path_01.txt AC 579 ms 70652 KiB
03_random_00.txt AC 562 ms 69824 KiB
03_random_01.txt AC 563 ms 70056 KiB
03_random_02.txt AC 537 ms 69584 KiB
04_perfect_00.txt AC 530 ms 68440 KiB