Submission #3231956


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }


    struct Edge : IComparable<Edge>
    {
        public int from, to, id; public long cost;
        public Edge(int from, int to, long cost)
        {
            this.from = from;
            this.to = to;
            this.cost = cost;
            id = -1;
        }
        public void set_id(int id)
        {
            this.id = id;
        }
        public int CompareTo(Edge e)
        {
            return cost.CompareTo(e.cost);
        }
    }
    void dfs(int u, long d, int p)
    {
        if (flag > 0) return;
        A[u] = d;
        B[u] = p;
        //WriteLine(u + " " + A[u] + " " + B[u]);
        //頂点uはd + p * t
        foreach (var v in G[u])
        {
            long next_d = v.cost - d;
            int next_p = p * -1;
            //行ったことがない
            if (B[v.to] == 0)
            {
                dfs(v.to, next_d, next_p);
            }
            else if (B[v.to] == next_p)
            {
                if (A[v.to] != next_d)
                {
                    flag = 1;
                    return;
                }
            }
            else
            {
                var tt = next_d * -1 * next_p + A[v.to] * -1 * B[v.to];
                //WriteLine(" " + u + " " + tt);
                if (tt % 2 == 1)
                {
                    flag = 1;
                    return;
                }
                else
                {
                    id = v.to;
                    X = tt / 2;
                    flag = 2;
                    return;
                }

            }
        }
    }

    long[] J;
    List<Edge>[] G;
    long[] A;
    long[] B;
    int flag = 0;
    int id = -1;
    long X = -1;
    void solve()
    {
        int N = cin.nextint;
        int M = cin.nextint;
        G = Enumerable.Range(0, N).Select(i => new List<Edge>()).ToArray();

        for (int i = 0; i < M; i++)
        {
            int u = cin.nextint - 1;
            int v = cin.nextint - 1;
            var c = cin.nextlong;
            G[u].Add(new Edge(u, v, c));
            G[v].Add(new Edge(v, u, c));
        }
        A = new long[N];
        B = new long[N];

        dfs(0, 0, 1);
        //WriteLine(flag + " " + id + " " + X);

        if (flag == 1)
        {
            WriteLine(0);
        }
        else if (flag == 2)
        {
            J = new long[N];
            for (int i = 0; i < N; i++)
            {
                J[i] = long.MinValue;
            }
            dfs2(0, X);
            if (J.Min() > 0 && flag != 4)
            {
                WriteLine(1);
            }
            else
            {
                WriteLine(0);
            }
        }
        else
        {
            long tmin = long.MinValue;
            long tmax = long.MaxValue;
            for (int i = 0; i < N; i++)
            {
                if (B[i] == 1)
                {
                    chmax(ref tmin, 1 - A[i]);
                }
                else
                {
                    chmin(ref tmax, A[i] - 1);
                }
            }

            WriteLine(Math.Max(0, tmax - tmin + 1));
        }
    }
    void dfs2(int u, long val)
    {
        J[u] = val;
        foreach (var v in G[u])
        {
            if (J[v.to] == long.MinValue)
            {
                dfs2(v.to, v.cost - val);
            }
            else
            {
                //整合性とれてるか確認
                if (J[v.to] != v.cost - val)
                {
                    flag = 4;
                }
            }
        }
    }
}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Submission Info

Submission Time
Task E - + Graph
User claw88
Language C# (Mono 4.6.2.0)
Score 600
Code Size 5524 Byte
Status AC
Exec Time 255 ms
Memory 53420 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 58
Set Name Test Cases
Sample sampleNo.txt, samplePath.txt, sampleTri.txt
All OK_0.txt, OK_1.txt, OK_2.txt, OK_3.txt, OK_4.txt, close_0.txt, close_1.txt, close_2.txt, close_3.txt, close_4.txt, many_0.txt, many_1.txt, many_2.txt, many_3.txt, many_4.txt, many_5.txt, many_6.txt, many_7.txt, max.txt, maxBip.txt, multiple_0.txt, multiple_1.txt, multiple_2.txt, multiple_3.txt, multiple_4.txt, multiple_5.txt, multiple_6.txt, multiple_7.txt, oddLoop.txt, oddLoop_0.txt, oddLoop_1.txt, oddLoop_2.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_8.txt, rnd_9.txt, sampleNo.txt, samplePath.txt, sampleTri.txt, star.txt, star_0.txt, star_1.txt, unique_0.txt, unique_1.txt, unique_2.txt, unique_3.txt, unique_4.txt, unique_5.txt, unique_6.txt, unique_7.txt, unique_8.txt, unique_9.txt
Case Name Status Exec Time Memory
OK_0.txt AC 232 ms 37772 KB
OK_1.txt AC 229 ms 35592 KB
OK_2.txt AC 233 ms 39692 KB
OK_3.txt AC 231 ms 41736 KB
OK_4.txt AC 235 ms 37640 KB
close_0.txt AC 221 ms 38388 KB
close_1.txt AC 220 ms 35964 KB
close_2.txt AC 217 ms 34212 KB
close_3.txt AC 224 ms 35016 KB
close_4.txt AC 242 ms 38728 KB
many_0.txt AC 219 ms 34840 KB
many_1.txt AC 219 ms 32920 KB
many_2.txt AC 216 ms 34340 KB
many_3.txt AC 214 ms 34084 KB
many_4.txt AC 217 ms 37924 KB
many_5.txt AC 222 ms 34084 KB
many_6.txt AC 217 ms 34340 KB
many_7.txt AC 217 ms 34836 KB
max.txt AC 167 ms 28860 KB
maxBip.txt AC 180 ms 28704 KB
multiple_0.txt AC 241 ms 36240 KB
multiple_1.txt AC 240 ms 39068 KB
multiple_2.txt AC 255 ms 38932 KB
multiple_3.txt AC 238 ms 34708 KB
multiple_4.txt AC 240 ms 34840 KB
multiple_5.txt AC 240 ms 34712 KB
multiple_6.txt AC 251 ms 34836 KB
multiple_7.txt AC 248 ms 37016 KB
oddLoop.txt AC 255 ms 49548 KB
oddLoop_0.txt AC 253 ms 53420 KB
oddLoop_1.txt AC 162 ms 40224 KB
oddLoop_2.txt AC 233 ms 44672 KB
rnd_0.txt AC 244 ms 39464 KB
rnd_1.txt AC 241 ms 37112 KB
rnd_2.txt AC 252 ms 39000 KB
rnd_3.txt AC 238 ms 38840 KB
rnd_4.txt AC 233 ms 38152 KB
rnd_5.txt AC 204 ms 31832 KB
rnd_6.txt AC 245 ms 36456 KB
rnd_7.txt AC 229 ms 33896 KB
rnd_8.txt AC 218 ms 33652 KB
rnd_9.txt AC 187 ms 34080 KB
sampleNo.txt AC 27 ms 11476 KB
samplePath.txt AC 27 ms 11476 KB
sampleTri.txt AC 28 ms 11476 KB
star.txt AC 229 ms 36024 KB
star_0.txt AC 232 ms 36036 KB
star_1.txt AC 227 ms 38076 KB
unique_0.txt AC 214 ms 32948 KB
unique_1.txt AC 214 ms 34996 KB
unique_2.txt AC 217 ms 37172 KB
unique_3.txt AC 217 ms 32948 KB
unique_4.txt AC 213 ms 35124 KB
unique_5.txt AC 215 ms 34996 KB
unique_6.txt AC 214 ms 34996 KB
unique_7.txt AC 212 ms 37044 KB
unique_8.txt AC 214 ms 35124 KB
unique_9.txt AC 214 ms 32948 KB