Submission #1271965


Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using Number = System.Int64;
using static System.Math;
using P = System.Int64;
namespace Program
{
    public class Solver
    {
        const int B = 32;
        const long M = (1L << 32) - 1;
        const long U = ~M;
        public void Solve()
        {

            var n = ri;
            var G = Enumerate(n, x => new List<KeyValuePair<int, int>>());
            for (int i = 0; i < n - 1; i++)
            {
                var a = ri - 1;
                var b = i + 1;
                var w = ri;
                G[a].Add(new KeyValuePair<int, int>(b, w));
            }
            Func<List<P>, List<P>, List<P>> g = (a, b) =>
            {
                var ret = new List<P>();
                var min = 1000000000000000;
                int i = 0, j = 0;
                while (i < a.Count && j < b.Count)
                {
                    var l = a[i];
                    var r = b[j];
                    if (min <= (l & M)) { i++; continue; }
                    if (min <= (r & M)) { j++; continue; }
                    if (l.CompareTo(r) <= 0) { i++; min = (l & M); ret.Add(l); }
                    else { j++; min = (r & M); ret.Add(r); }
                }
                while (i < a.Count)
                {
                    if (min <= (a[i] & M)) i++;
                    else { min = (a[i] & M); ret.Add(a[i++]); }
                }
                while (j < b.Count)
                {
                    if (min <= (b[j] & M)) j++;
                    else { min = (b[j] & M); ret.Add(b[j++]); }
                }

                return ret;
            };
            Func<int, long, List<P>> f = null;
            f = (cur, x) =>
            {
                if (G[cur].Count == 0) return new List<P>() { 0 };
                var a = new List<P>();
                var l = f(G[cur][0].Key, x);
                if (l.Count == 0) return a;
                var r = f(G[cur][1].Key, x);
                if (r.Count == 0) return a;
                var u = G[cur][0].Value;
                var v = G[cur][1].Value;
                var b = new List<P>();

                if (l.Count > r.Count) { Swap(ref l, ref r); Swap(ref u, ref v); }
                var i = 0; var j = 0; var k = 0;
                while (i < l.Count)
                {
                    while (j < r.Count && (l[i] >> B) + (r[j] & M) + u + v > x) j++;
                    while (k + 1 < r.Count && (l[i] & M) + (r[k + 1] >> B) + u + v <= x) k++;
                    if (k < r.Count && (l[i] & M) + (r[k] >> B) + u + v <= x) a.Add((((l[i] >> B) + u) << B) + (r[k] & M) + v);
                    if (j < r.Count) b.Add((((r[j] >> B) + v) << B) + ((l[i] & M) + u));
                    i++;
                }

                var ret = g(a, b);
                //Debug.WriteLine($"[{cur}], {ret.AsJoinedString()}");
                return ret;
            };

            {
                long l = -1, r = 5000000;
                while (r - l > 1)
                {
                    var m = (l + r) / 2;
                    if (f(0, m).Count != 0) r = m;
                    else l = m;
                }
                IO.Printer.Out.WriteLine(r);
            }
        }
        int ri => sc.Integer();
        long rl => sc.Long();
        double rd => sc.Double();
        string rs => sc.Scan();


        public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
        static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
    }
}

#region main
static class Ex
{
    static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
    static public void Main()
    {
        var solver = new Program.Solver();
        solver.Solve();
        Program.IO.Printer.Out.Flush();
    }
}
#endregion
#region Ex
namespace Program.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;
    public class Printer: StreamWriter
    {
        static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
        public static Printer Out { get; set; }
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
        public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
        public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
        public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        public readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) return 0;
            if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
            return buf[ptr++];
        }
        public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }

        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public string ScanLine()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b != '\n'; b = (char)read())
                if (b == 0) break;
                else if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            if (isEof) return long.MinValue;
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != 0 && b != '-' && (b < '0' || '9' < b));
            if (b == 0) return long.MinValue;
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
        public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
        private T[] enumerate<T>(int n, Func<T> f)
        {
            var a = new T[n];
            for (int i = 0; i < n; ++i) a[i] = f();
            return a;
        }

        public char[] Char(int n) { return enumerate(n, Char); }
        public string[] Scan(int n) { return enumerate(n, Scan); }
        public double[] Double(int n) { return enumerate(n, Double); }
        public int[] Integer(int n) { return enumerate(n, Integer); }
        public long[] Long(int n) { return enumerate(n, Long); }
    }
}
#endregion
#region Compair
static public class Pair
{
    static public Pair<FT, ST> Create<FT, ST>(FT f, ST s) where FT : IComparable<FT> where ST : IComparable<ST>
    {
        return new Pair<FT, ST>(f, s);
    }
    static public Pair<FT, ST> Min<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q) where FT : IComparable<FT> where ST : IComparable<ST>
    {
        return (p.CompareTo(q) <= 0) ? p : q;
    }
    static public Pair<FT, ST> Max<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q) where FT : IComparable<FT> where ST : IComparable<ST>
    {
        return (p.CompareTo(q) >= 0) ? p : q;
    }
}
public struct Pair<FT, ST>: IComparable<Pair<FT, ST>> where FT : IComparable<FT> where ST : IComparable<ST>
{
    public FT x;
    public ST y;
    public Pair(FT f, ST s) : this() { x = f; y = s; }

    public int CompareTo(Pair<FT, ST> other)
    {
        var cmp = x.CompareTo(other.x);
        return cmp != 0 ? cmp : y.CompareTo(other.y);
    }
    public override string ToString() { return string.Format("[{0} {1}]", x, y); }
}
#endregion

Submission Info

Submission Time
Task E - Shik and Travel
User camypaper
Language C# (Mono 4.6.2.0)
Score 0
Code Size 8740 Byte
Status TLE
Exec Time 5261 ms
Memory 49180 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 4
AC × 49
TLE × 5
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt, example3.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt AC 32 ms 15668 KB
001.txt AC 32 ms 15668 KB
002.txt AC 33 ms 17716 KB
003.txt AC 31 ms 15672 KB
004.txt AC 32 ms 15668 KB
005.txt AC 31 ms 15668 KB
006.txt AC 31 ms 15668 KB
007.txt AC 31 ms 13620 KB
008.txt AC 32 ms 15668 KB
009.txt AC 32 ms 15668 KB
010.txt AC 492 ms 23908 KB
011.txt AC 486 ms 23876 KB
012.txt AC 478 ms 25952 KB
013.txt AC 498 ms 23924 KB
014.txt AC 452 ms 25924 KB
015.txt AC 488 ms 30024 KB
016.txt AC 520 ms 25924 KB
017.txt AC 513 ms 25952 KB
018.txt AC 494 ms 28000 KB
019.txt AC 432 ms 25916 KB
020.txt AC 500 ms 25932 KB
021.txt AC 494 ms 25928 KB
022.txt AC 488 ms 23920 KB
023.txt AC 497 ms 25932 KB
024.txt AC 476 ms 23880 KB
025.txt AC 397 ms 30008 KB
026.txt AC 437 ms 30008 KB
027.txt AC 495 ms 25928 KB
028.txt AC 468 ms 25916 KB
029.txt AC 408 ms 27972 KB
030.txt AC 482 ms 23868 KB
031.txt AC 517 ms 23908 KB
032.txt AC 533 ms 25912 KB
033.txt AC 437 ms 25904 KB
034.txt AC 520 ms 27980 KB
035.txt AC 515 ms 30012 KB
036.txt AC 482 ms 25912 KB
037.txt AC 462 ms 25936 KB
038.txt AC 480 ms 25936 KB
039.txt AC 431 ms 23852 KB
040.txt AC 728 ms 48048 KB
041.txt AC 754 ms 46068 KB
042.txt AC 756 ms 49180 KB
043.txt AC 749 ms 46052 KB
044.txt TLE 5261 ms 30744 KB
045.txt TLE 5260 ms 30744 KB
046.txt TLE 5261 ms 32792 KB
047.txt TLE 5261 ms 34840 KB
048.txt TLE 5261 ms 30744 KB
049.txt AC 23 ms 9428 KB
example0.txt AC 24 ms 11476 KB
example1.txt AC 24 ms 9428 KB
example2.txt AC 24 ms 11476 KB
example3.txt AC 23 ms 9428 KB