Submission #1092767


Source Code Expand

Copy
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;

class Myon
{
    static Scanner cin;
    public Myon() { }
    public static int Main()
    {
        cin = new Scanner();
        new Myon().calc();
        return 0;
    }

    int N;
    long[] A;
    List<int>[] es;
    
    public bool calc2()
    {
        N = cin.nextInt();
        A = new long[N];
        for (int i = 0; i < N; i++)
        {
            A[i] = cin.nextLong();
        }
        es = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            es[i] = new List<int>();
        }

        for (int i = 0; i < N - 1; i++)
        {
            int a = cin.nextInt() - 1;
            int b = cin.nextInt() - 1;
            es[a].Add(b);
            es[b].Add(a);
        }


        max = new long[N];
        min = new long[N];
        if (!dfs(0, -1)) return false;
        if (max[0] >= 0 && min[0] <= 0) return true;
        return false;
    }

    long[] max, min;

    bool dfs(int now, int pre)
    {
        long T = A[now];

        foreach (var next in es[now])
        {
            if (next == pre) continue;
            if (!dfs(next, now)) break;
        }

        long minsum = 0;
        foreach (var next in es[now])
        {
            if (next == pre) continue;
            minsum += min[next];
            if (min[next] > T) return false;
        }
        if (minsum > 2 * T) return false;

        long maxsum = 0;
        foreach (var next in es[now])
        {
            maxsum += Math.Min(T, max[next]);
        }

        if(es[now].Count == 1)
        {
            min[now] = Math.Max(0, T - maxsum);
            max[now] = Math.Min(T, 2 * T - minsum);
        }
        else
        {
            min[now] = Math.Max(0, 2 * T - maxsum);
            max[now] = Math.Min(T, 2 * T - minsum);
        }

        if (min[now] > max[now]) return false;
        return true;
    }

    public void calc()
    {
        if (calc2()) Console.WriteLine("YES");
        else Console.WriteLine("NO");
    }
    
}

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

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

    public string next()
    {
        while (i >= s.Length)
        {
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
        }
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Submission Info

Submission Time
Task C - Cleaning
User chokudai
Language C# (Mono 4.6.2.0)
Score 700
Code Size 2989 Byte
Status
Exec Time 239 ms
Memory 44776 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 700 / 700 sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt
Case Name Status Exec Time Memory
in1.txt 228 ms 23932 KB
in10.txt 218 ms 23804 KB
in11.txt 236 ms 36412 KB
in12.txt 239 ms 36408 KB
in13.txt 221 ms 44776 KB
in14.txt 218 ms 41832 KB
in15.txt 21 ms 2776 KB
in16.txt 21 ms 2776 KB
in17.txt 21 ms 2776 KB
in18.txt 21 ms 2776 KB
in19.txt 205 ms 23804 KB
in2.txt 214 ms 23804 KB
in20.txt 198 ms 23424 KB
in21.txt 197 ms 23552 KB
in22.txt 202 ms 23800 KB
in23.txt 214 ms 23800 KB
in24.txt 215 ms 23800 KB
in25.txt 21 ms 2776 KB
in26.txt 202 ms 23752 KB
in27.txt 207 ms 23752 KB
in28.txt 21 ms 2776 KB
in29.txt 190 ms 24800 KB
in3.txt 215 ms 23804 KB
in30.txt 21 ms 2776 KB
in31.txt 213 ms 23804 KB
in32.txt 206 ms 23804 KB
in33.txt 219 ms 23800 KB
in34.txt 216 ms 23804 KB
in35.txt 221 ms 23800 KB
in36.txt 220 ms 23804 KB
in37.txt 23 ms 3288 KB
in38.txt 216 ms 23800 KB
in39.txt 220 ms 23800 KB
in4.txt 227 ms 23800 KB
in40.txt 209 ms 23804 KB
in41.txt 207 ms 23804 KB
in42.txt 224 ms 23804 KB
in43.txt 219 ms 23800 KB
in44.txt 235 ms 23800 KB
in45.txt 226 ms 23804 KB
in5.txt 224 ms 23804 KB
in6.txt 214 ms 23804 KB
in7.txt 198 ms 23192 KB
in8.txt 69 ms 11992 KB
in9.txt 218 ms 23800 KB
sample1.txt 21 ms 2776 KB
sample2.txt 21 ms 2776 KB
sample3.txt 21 ms 2776 KB