ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1450. Russian Pipelines

Hints for all who has TL and especially for C# and Java coders
Posted by Leonid (SLenik) Andrievskiy 16 Sep 2011 05:42
0. Use DFS to find all vertices reachable from the start and exclude others from further steps.
1. Use O(m + n) algo.
2. [For C# coders] do not use List or SortedList or even Dictionary! And do not use foreach!
3. Use the fastest input parser you have. For example my parser looks like this:

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace _1450__acm.timus.ru_
{
    class SerialInput
    {
        private static Dictionary<int, int> separators =
            new Dictionary<int, int> { { ' ', 0 }, { '\n', 0 }, { '\r', 0 } };

        private StreamReader reader;

        public SerialInput(StreamReader reader)
        {
            this.reader = reader;
        }
        public int ReadInt()
        {
            while (separators.ContainsKey(reader.Peek()))
                reader.Read();
            int symbol = reader.Read();
            int value = 0;
            while ((symbol != -1) && !separators.ContainsKey(symbol))
            {
                value = value * 10 + (symbol - '0');
                symbol = reader.Read();
            }
            return value;
        }
    }
    class Program
    {
        static void Main()
        {
            const int InputBufferSize = 65536;
            const int OutputBufferSize = 65536;

#if (ONLINE_JUDGE)
            var input = new SerialInput(
                new StreamReader(Console.OpenStandardInput(InputBufferSize)));
            var output = new StreamWriter(Console.OpenStandardOutput(OutputBufferSize));
#else
            var input = new SerialInput(
                new StreamReader(new FileStream(@"..\..\input.txt",
                    FileMode.Open, FileAccess.Read, FileShare.Read,
                    InputBufferSize)));
            var output = new StreamWriter(new FileStream(@"..\..\output.txt",
                    FileMode.Create, FileAccess.Write, FileShare.Write,
                    OutputBufferSize));
#endif

            int n = input.ReadInt(), m = input.ReadInt();

            // write your code here

            output.Flush();
        }
    }
}