Contest Duration: ~ (local time) (90 minutes) Back to Home

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();
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++)
{
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;
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) { }
{
}
}
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 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
{
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)
{
}
public void Read<S, T, U>(out S s, out T t, out U u)
{
}
{
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 2015-10-11 00:03:48+0900 C - エックスオア多橋君 selpo C# (Mono 3.2.1.0) 100 6267 Byte AC 1273 ms 87020 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory