Submission #524944


Source Code Expand

Copy
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Problem
{
	private int N;
	private int X;
	private Tuple<int, int, int>[] edge;
	public Problem()
	{
		var sc = new Scan();
		sc.Read(out N, out X);
		edge = Enumerable.Range(0, N - 1).Select(_ => sc.ReadTuple<int, int, int>()).ToArray();
	}
	private List<Tuple<int, int>>[] children;
	private UndirectedGraph<int, int> graph;
	public void Solve()
	{
		using (var pr = new Printer())
		{
			graph = new UndirectedGraph<int, int>(N);
			foreach (var e in edge) graph.AddEdge(e.Item1 - 1, e.Item2 - 1, e.Item3);
			InitiateChildren();
			Colorize();

			var count = 0L;
			var dict = new Dictionary<int, int>();
			for (var v = 0; v < N; v++)
			{
				if (!dict.ContainsKey(graph[v])) dict.Add(graph[v], 0);
				dict[graph[v]]++;
			}
			if (X == 0) foreach (var key in dict) count += (long)key.Value * (key.Value - 1);
			else foreach (var key in dict) if (dict.ContainsKey(key.Key ^ X)) count += dict[key.Key ^ X] * key.Value;
			pr.WriteLine(count >> 1);
		}
	}
	private void Colorize()
	{
		var stack = new Stack<int>();
		stack.Push(0);
		while (stack.Count > 0)
		{
			var v = stack.Pop();
			foreach (var w in children[v])
			{
				graph[w.Item1] = graph[v] ^ w.Item2;
				stack.Push(w.Item1);
			}
		}
	}
	private void InitiateChildren()
	{
		children = new List<Tuple<int, int>>[N];
		for (var v = 0; v < N; v++) children[v] = new List<Tuple<int, int>>();
		var used = new bool[N];
		var queue = new Queue<int>();
		queue.Enqueue(0);
		used[0] = true;
		while (queue.Count > 0)
		{
			var v = queue.Dequeue();
			foreach (var w in graph.EdgesFrom(v))
			{
				if (!used[w.End])
				{
					used[w.End] = true;
					children[v].Add(new Tuple<int, int>(w.End, w.Information));
					queue.Enqueue(w.End);
				}
			}
		}
	}
}
class Program
{
	static void Main()
	{
		new Problem().Solve();
	}
}
class UndirectedGraph<V, E> : DirectedGraph<V, E>
{
	public UndirectedGraph(int V) : base(V) { }
	public override void AddEdge(EdgeInfo<E> edge)
	{
		edges.Add(edge);
		edgeFrom[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
		edgeFrom[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
		edgeTo[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
		edgeTo[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
	}
}
class NodeInfo<V> : Pair<int, V>
{
	public int Code { get { return First; } set { First = value; } }
	public V Information { get { return Second; } set { Second = value; } }
	public NodeInfo(int code, V info) : base(code, info) { }
}
class HalfEdgeInfo<E> : Pair<int, E>
{
	public int End { get { return First; } set { First = value; } }
	public E Information { get { return Second; } set { Second = value; } }
	public HalfEdgeInfo(int end, E info) : base(end, info) { }
}
class EdgeInfo<E> : Pair<Pair<int, int>, E>
{
	public int From { get { return First.First; } set { First.First = value; } }
	public int To { get { return First.Second; } set { First.Second = value; } }
	public E Information { get { return Second; } set { Second = value; } }
	public EdgeInfo(int from, int to, E info) : base(new Pair<int, int>(from, to), info) { }
}
class DirectedGraph<V, E>
{
	protected int numberOfNodes;
	protected NodeInfo<V>[] nodes;
	protected List<EdgeInfo<E>> edges;
	protected List<HalfEdgeInfo<E>>[] edgeFrom;
	protected List<HalfEdgeInfo<E>>[] edgeTo;
	public IEnumerable<HalfEdgeInfo<E>> EdgesFrom(int node) { return edgeFrom[node]; }
	public IEnumerable<HalfEdgeInfo<E>> EdgesTo(int node) { return edgeTo[node]; }
	public V this[int node] { get { return nodes[node].Second; } set { nodes[node].Second = value; } }
	public DirectedGraph(int V)
	{
		numberOfNodes = V;
		nodes = Enumerable.Range(0, V).Select(x => new NodeInfo<V>(x, default(V))).ToArray();
		edges = new List<EdgeInfo<E>>();
		edgeFrom = Enumerable.Range(0, V).Select(_ => new List<HalfEdgeInfo<E>>()).ToArray();
		edgeTo = Enumerable.Range(0, V).Select(_ => new List<HalfEdgeInfo<E>>()).ToArray();
	}
	public virtual void AddEdge(EdgeInfo<E> edge)
	{
		edges.Add(edge);
		edgeFrom[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
		edgeTo[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
	}
	public void AddEdge(int from, int to, E information) { AddEdge(new EdgeInfo<E>(from, to, information)); }
}
class Pair<S, T>
{
	public S First;
	public T Second;
	public Pair(S s, T t) { First = s; Second = t; }
}
class Printer : IDisposable
{
	private TextWriter file;
	public Printer() { file = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; }
	public void WriteLine<T>(T value) { file.WriteLine(value); }
	public void Dispose() { file.Flush(); }
}
class Scan
{
	private TextReader file;
	public Scan() { file = Console.In; }
	public Pair<S, T> ReadPair<S, T>() { S s; T t; Read(out s, out t); return new Pair<S, T>(s, t); }
	public Tuple<S, T, U> ReadTuple<S, T, U>() { S s; T t; U u; Read(out s, out t, out u); return new Tuple<S, T, U>(s, t, u); }
	public void Read<S, T>(out S s, out T t)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
	}
	public void Read<S, T, U>(out S s, out T t, out U u)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
		u = (U)read[2];
	}
	private IEnumerable<object> ReadMulti(params TypeCode[] types)
	{
		var inp = file.ReadLine().Split(' ');
		for (var i = 0; i < types.Length; i++)
		{
			if (types[i] == TypeCode.Int32) yield return int.Parse(inp[i]);
			else if (types[i] == TypeCode.UInt32) yield return uint.Parse(inp[i]);
			else if (types[i] == TypeCode.Int64) yield return long.Parse(inp[i]);
			else if (types[i] == TypeCode.Double) yield return double.Parse(inp[i]);
			else if (types[i] == TypeCode.Decimal) yield return decimal.Parse(inp[i]);
			else if (types[i] == TypeCode.String) yield return inp[i];
			else throw new Exception();
		}
	}
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User selpo
Language C# (Mono 3.2.1.0)
Score 100
Code Size 6267 Byte
Status
Exec Time 1273 ms
Memory 87020 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 100 / 100 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 170 ms 10632 KB
subtask0_sample_02.txt 167 ms 10632 KB
subtask0_sample_03.txt 166 ms 10624 KB
subtask1_01.txt 163 ms 10508 KB
subtask1_02.txt 175 ms 11780 KB
subtask1_03.txt 1270 ms 87020 KB
subtask1_04.txt 1228 ms 86892 KB
subtask1_05.txt 1214 ms 86900 KB
subtask1_06.txt 817 ms 83964 KB
subtask1_07.txt 1052 ms 81148 KB
subtask1_08.txt 1073 ms 81136 KB
subtask1_09.txt 1273 ms 82836 KB
subtask1_10.txt 1244 ms 83064 KB
subtask1_11.txt 183 ms 11808 KB
subtask1_12.txt 182 ms 11816 KB
subtask1_13.txt 1239 ms 82924 KB
subtask1_14.txt 1187 ms 83116 KB
subtask1_15.txt 240 ms 19436 KB
subtask1_16.txt 243 ms 19484 KB
subtask1_17.txt 238 ms 19428 KB
subtask1_18.txt 235 ms 19484 KB
subtask1_19.txt 234 ms 19480 KB
subtask1_20.txt 239 ms 19560 KB
subtask1_21.txt 242 ms 19548 KB
subtask1_22.txt 236 ms 19464 KB
subtask1_23.txt 235 ms 19560 KB
subtask1_24.txt 236 ms 19432 KB