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 |
|
|
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 |