Submission #524346


Source Code Expand

Copy
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Problem
{
	private int N;
	private int X;
	private Tuple<int, int, int>[] edge;
	public int Size { get { return N; } }
	public Problem()
	{
		using (var sc = new Scan(true))
		{
			sc.Read(out N, out X);
			edge = Enumerable.Range(0, N - 1).Select(_ => sc.ReadTuple<int, int, int>()).ToArray();
		}
	}
	private bool[] selectType;
	private List<Tuple<int, bool[]>>[] children;
	private UndirectedGraph<bool[], bool[]> graph;
	public void Solve()
	{
		using (var pr = new Printer())
		{
			selectType = new bool[30];
			var tmp = X;
			for (var b = 0; b < 30; b++)
			{
				selectType[b] = (tmp & 1) == 1;
				tmp >>= 1;
			}
			InitiateGraph();
			InitiateChildren();
			Colorize();
			var nodes = new int[N];
			for (var v = 0; v < N; v++)
				for (var b = 30 - 1; b >= 0; b--)
					nodes[v] = (nodes[v] << 1) | (graph[v][b] ? 1 : 0);
			var count = 0L;
			for (var v = 0; v < N; v++)
				for (var w = 0; w < v; w++)
					if ((nodes[v] ^ nodes[w]) == X)
						count++;
			pr.WriteLine(count);
		}
	}
	private void InitiateGraph()
	{
		graph = new UndirectedGraph<bool[], bool[]>(N);
		for (var v = 0; v < N; v++) graph[v] = new bool[30];
		foreach (var e in edge)
		{
			var tmp = new bool[30];
			var cost = e.Item3;
			for (var b = 0; b < 30; b++)
			{
				tmp[b] = (cost & 1) == 1;
				cost >>= 1;
			}
			graph.AddEdge(e.Item1 - 1, e.Item2 - 1, tmp);
		}
	}
	private void Colorize()
	{
		for (var b = 0; b < 30; b++)
		{
			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][b] = graph[v][b] ^ w.Item2[b];
					stack.Push(w.Item1);
				}
			}
		}
	}
	private void InitiateChildren()
	{
		children = new List<Tuple<int, bool[]>>[N];
		for (var v = 0; v < N; v++) children[v] = new List<Tuple<int, bool[]>>();
		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, bool[]>(w.End, w.Information));
					queue.Enqueue(w.End);
				}
			}
		}
	}
}
class Program
{
	public static Random rand = new Random();
	public static bool IsJudgeMode = true;
	static void Main()
	{
		if (IsJudgeMode) new Problem().Solve();
		else
		{
			int num = 2;
			int size = 0;
			decimal time = 0;
			for (var tmp = 0; tmp < num; tmp++)
			{
				var P = new Problem();
				size = P.Size;
				time += Func.MeasureTime(() => P.Solve());
			}
			Console.WriteLine("{0}, {1}ms", size, time / num);
		}
	}
}
class UndirectedGraph<V, E> : DirectedGraph<V, E>
{
	public UndirectedGraph(int V) : base(V) { }
	public UndirectedGraph(int V, IEnumerable<EdgeInfo<E>> edges) : base(V, edges) { }
	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));
	}
	public bool IsConnected
	{
		get
		{
			if (numberOfNodes == 0) return true;
			var used = new bool[numberOfNodes];
			var queue = new Queue<int>();
			queue.Enqueue(0);
			while (queue.Count > 0)
			{
				var v = queue.Dequeue();
				if (used[v]) continue;
				used[v] = true;
				foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
			}
			return used.All(x => x);
		}
	}
	public bool IsTree
	{
		get
		{
			if (numberOfNodes == 0) return true;
			var used = new bool[numberOfNodes];
			var queue = new Queue<int>();
			queue.Enqueue(0);
			while (queue.Count > 0)
			{
				var v = queue.Dequeue();
				if (used[v]) return false;
				used[v] = true;
				foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
			}
			return used.All(x => x);
		}
	}
	public UndirectedGraph<V, E> MinimumSpanningTreePrim(int start, Func<E, int> cost)
	{
		var graph = new UndirectedGraph<V, E>(numberOfNodes);
		nodes.CopyTo(graph.nodes, 0);
		var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
		var used = new bool[numberOfNodes];
		var queue = new PriorityQueue<Pair<EdgeInfo<E>, int>>((x, y) => x.Second.CompareTo(y.Second), numberOfNodes);
		d[start] = 0;
		queue.Enqueue(new Pair<EdgeInfo<E>, int>(new EdgeInfo<E>(-1, 0, default(E)), 0));
		while (queue.Count > 0)
		{
			var p = queue.Dequeue();
			var v = p.First.To;
			if (d[v] < p.Second) continue;
			used[v] = true;
			if (p.First.From >= 0) graph.AddEdge(v, p.First.From, p.First.Information);
			foreach (var w in EdgesFrom(v))
			{
				if (!used[w.End] && cost(w.Information) < d[w.End])
				{
					d[w.End] = cost(w.Information);
					queue.Enqueue(new Pair<EdgeInfo<E>, int>(new EdgeInfo<E>(v, w.End, w.Information), cost(w.Information)));
				}
			}
		}
		return graph;
	}
	public UndirectedGraph<V, E> MinimumSpanningTreeKruskal(Func<E, int> cost)
	{
		var graph = new UndirectedGraph<V, E>(numberOfNodes);
		nodes.CopyTo(graph.nodes, 0);
		var tree = new UnionFindTree(numberOfNodes);
		edges.Sort((x, y) => cost(x.Information).CompareTo(cost(y.Information)));
		foreach (var e in edges)
		{
			if (!tree.IsSameCategory(e.From, e.To))
			{
				tree.UniteCategory(e.From, e.To);
				graph.AddEdge(e);
			}
		}
		return graph;
	}
	public bool IsBipartite
	{
		get
		{
			var color = new int[numberOfNodes];
			foreach (var v in nodes)
			{
				if (color[v.Code] == 0)
				{
					var queue = new Queue<Pair<int, int>>();
					queue.Enqueue(new Pair<int, int>(v.Code, 1));
					while (queue.Count > 0)
					{
						var w = queue.Dequeue();
						if (color[w.First] != 0)
						{
							if (color[w.First] != w.Second)
								return false;
							continue;
						}
						color[w.First] = w.Second;
						foreach (var e in EdgesFrom(w.First)) queue.Enqueue(new Pair<int, int>(e.End, -w.Second));
					}
				}
			}
			return true;
		}
	}
	public string ToString(Func<NodeInfo<V>, string> vertex, Func<EdgeInfo<E>, string> edge)
	{
		var sb = new StringBuilder();
		sb.Append("graph G {\n");
		foreach (var v in nodes) sb.Append("\tv" + v.Code + " [label = \"" + vertex(v) + "\"];\n");
		foreach (var e in edges) sb.Append("\tv" + e.From + " -- v" + e.To + " [label=\"" + edge(e) + "\"];\n");
		sb.Append("}");
		return sb.ToString();
	}
	public override string ToString() { return ToString(v => v.ToString(), e => e.ToString()); }
}
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() : base() { }
	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() : base() { }
	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() : base() { }
	public EdgeInfo(int from, int to, E info) : base(new Pair<int, int>(from, to), info) { }
}
class DirectedGraph<V, E> : IEnumerable<NodeInfo<V>>
{
	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 int InDegree(int node) { return edgeTo[node].Count; }
	public int OutDegree(int node) { return edgeFrom[node].Count; }
	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 IEnumerable<EdgeInfo<E>> Edges { get { return edges; } }
	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 DirectedGraph(int V, IEnumerable<EdgeInfo<E>> edges) : this(V) { foreach (var e in edges) AddEdge(e.From, e.To, e.Information); }
	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)); }
	public void AddEdge(V from, V to, E information) { AddEdge(new EdgeInfo<E>(SearchNode(from).Code, SearchNode(to).Code, information)); }
	public NodeInfo<V> SearchNode(V node) { return nodes.FirstOrDefault(e => e.Information.Equals(node)); }
	public EdgeInfo<E> SearchEdge(E edge) { return edges.Find(e => e.Information.Equals(edge)); }
	public IEnumerator<NodeInfo<V>> GetEnumerator() { foreach (var v in nodes) yield return v; }
	IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
	public int[] ShortestPathLengthFrom(int from, Func<E, int> cost)
	{
		var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
		d[from] = 0;
		var update = true;
		while (update)
		{
			update = false;
			foreach (var e in edges)
			{
				var tmp = d[e.From] + cost(e.Information);
				if (d[e.From] < Func.Inf && d[e.To] > tmp)
				{
					d[e.To] = tmp;
					update = true;
				}
			}
		}
		return d;
	}
	// cost(e)>=0
	public int[] DijkstraFrom(int from, Func<E, int> cost)
	{
		var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
		var queue = new PriorityQueue<Pair<int, int>>((x, y) => x.Second.CompareTo(y.Second));
		d[from] = 0;
		queue.Enqueue(new Pair<int, int>(from, 0));
		while (!queue.IsEmpty)
		{
			var p = queue.Dequeue();
			var v = p.First;
			if (d[v] < p.Second) continue;
			foreach (var e in EdgesFrom(v))
			{
				var tmp = d[v] + cost(e.Information);
				if (d[e.End] > tmp)
				{
					d[e.End] = tmp;
					queue.Enqueue(new Pair<int, int>(e.End, d[e.End]));
				}
			}
		}
		return d;
	}
	public int[,] ShortestPathLengthEachOther(Func<E, int> cost)
	{
		var d = new int[numberOfNodes, numberOfNodes];
		for (var v = 0; v < numberOfNodes; v++) for (var w = 0; w < numberOfNodes; w++) d[v, w] = Func.Inf;
		for (var v = 0; v < numberOfNodes; v++) d[v, v] = 0;
		foreach (var e in edges) if (e.From != e.To) d[e.From, e.To] = cost(e.Information);
		for (int k = 0; k < numberOfNodes; k++)
			for (int v = 0; v < numberOfNodes; v++)
				for (int w = 0; w < numberOfNodes; w++)
					d[v, w] = Math.Min(d[v, w], d[v, k] + d[k, w]);
		return d;
	}
	public bool ContainsNegativeLoopWF(Func<E, int> cost)
	{
		var d = ShortestPathLengthEachOther(cost);
		for (var v = 0; v < numberOfNodes; v++) if (d[v, v] < 0) return true;
		return false;
	}
	public bool ContainsNegativeLoop(Func<E, int> cost)
	{
		var d = Enumerable.Repeat(0, numberOfNodes).ToArray();
		for (var v = 0; v < numberOfNodes; v++)
		{
			foreach (var e in edges)
			{
				var tmp = d[e.From] + cost(e.Information);
				if (d[e.To] > tmp)
				{
					d[e.To] = tmp;
					if (v == numberOfNodes - 1) return true;
				}
			}
		}
		return false;
	}
	public IEnumerable<int> ReachableFrom(int from)
	{
		var used = new bool[numberOfNodes];
		var queue = new Queue<int>();
		queue.Enqueue(from);
		while (queue.Count > 0)
		{
			var v = queue.Dequeue();
			if (used[v]) continue;
			used[v] = true;
			foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
		}
		for (var v = 0; v < numberOfNodes; v++) if (used[v]) yield return v;
	}
	public bool IsReachable(int from, int to)
	{
		var used = new bool[numberOfNodes];
		var queue = new Queue<int>();
		queue.Enqueue(from);
		while (queue.Count > 0)
		{
			var v = queue.Dequeue();
			if (v == to) return true;
			if (used[v]) continue;
			used[v] = true;
			foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
		}
		return false;
	}
	public string ToString(Func<V, string> vertex, Func<E, string> edge)
	{
		var sb = new StringBuilder();
		sb.Append("digraph G {\n");
		foreach (var v in nodes) sb.Append("\tv" + v.Code + " [label = \"" + vertex(v.Information) + "\"];\n");
		foreach (var e in edges) sb.Append("\tv" + e.From + " -> v" + e.To + " [label=\"" + edge(e.Information) + "\"];\n");
		sb.Append("}");
		return sb.ToString();
	}
	public override string ToString() { return ToString(v => v.ToString(), e => e.ToString()); }
}
class UnionFindTree
{
	private int N;
	private List<int> parent;
	private List<int> rank;
	public UnionFindTree(int capacity)
	{
		parent = new List<int>(capacity);
		rank = new List<int>(capacity);
		N = capacity;
		for (int i = 0; i < capacity; i++)
		{
			parent.Add(i);
			rank.Add(0);
		}
	}
	public void Add(int x)
	{
		if (x >= N)
		{
			for (int i = N; i <= x; i++)
			{
				parent.Add(i);
				parent.Add(0);
			}
			N = x + 1;
		}
	}
	private int GetRootOf(int x)
	{
		Add(x);
		if (parent[x] == x) return x;
		else return parent[x] = GetRootOf(parent[x]);
	}
	public void UniteCategory(int x, int y)
	{
		x = GetRootOf(x);
		y = GetRootOf(y);
		if (x == y) return;
		if (rank[x] < rank[y]) parent[x] = y;
		else
		{
			parent[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
	public bool IsSameCategory(int x, int y) { return GetRootOf(x) == GetRootOf(y); }
}
class AVLTree<T> : IEnumerable<T>, ICollection<T>, ICollection, IEnumerable
{
	private class AVLNode : IEnumerable<T>
	{
		private AVLTree<T> tree;
		private int height;
		public int Height { get { return height; } }
		public int Bias { get { return Left.height - Right.height; } }
		public T Item;
		public AVLNode Parent;
		public AVLNode Left;
		public AVLNode Right;
		private AVLNode(T x, AVLTree<T> tree) { this.tree = tree; Item = x; Left = tree.sentinel; Right = tree.sentinel; }
		public AVLNode(AVLTree<T> tree) : this(default(T), tree) { height = 0; Parent = null; }
		public AVLNode(T x, AVLNode parent, AVLTree<T> tree) : this(x, tree) { this.height = 1; this.Parent = parent; }
		public void Adjust() { height = 1 + Math.Max(Left.height, Right.height); }
		public void ResetAsSentinel() { height = 0; Left = tree.sentinel; Right = tree.sentinel; }
		public IEnumerator<T> GetEnumerator()
		{
			if (this != tree.sentinel)
			{
				foreach (var x in Left) yield return x;
				yield return Item;
				foreach (var x in Right) yield return x;
			}
		}
		IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
	}
	private AVLNode sentinel;
	private Comparison<T> comp;
	private Func<T, T, bool> equals;
	private int count;
	// assumed to be comparer
	// i.e. comp(x,x)=0, and comp(x,y)>0 then comp(y,x)<0, and comp(x,y)>0 & comp(y,z)>0 then comp(x,z)>0
	public AVLTree(Comparison<T> comp)
	{
		sentinel = new AVLNode(this);
		sentinel.ResetAsSentinel();
		this.comp = comp;
		if (typeof(T).IsValueType) equals = (x, y) => x.Equals(y);
		else equals = (x, y) => ReferenceEquals(x, y);
		count = 0;
	}
	public AVLTree(IComparer<T> comp) : this((x, y) => comp.Compare(x, y)) { }
	private void Replace(AVLNode u, AVLNode v)
	{
		var parent = u.Parent;
		if (parent.Left == u) parent.Left = v;
		else parent.Right = v;
		v.Parent = parent;
	}
	private AVLNode RotateL(AVLNode v)
	{
		var u = v.Right;
		Replace(v, u);
		v.Right = u.Left;
		u.Left.Parent = v;
		u.Left = v;
		v.Parent = u;
		v.Adjust();
		u.Adjust();
		return u;
	}
	private AVLNode RotateR(AVLNode u)
	{
		var v = u.Left;
		Replace(u, v);
		u.Left = v.Right;
		v.Right.Parent = u;
		v.Right = u;
		u.Parent = v;
		u.Adjust();
		v.Adjust();
		return v;
	}
	private AVLNode RotateLR(AVLNode t) { RotateL(t.Left); return RotateR(t); }
	private AVLNode RotateRL(AVLNode t) { RotateR(t.Right); return RotateL(t); }
	private void Adjust(bool isInsertMode, AVLNode node)
	{
		while (node.Parent != sentinel)
		{
			var parent = node.Parent;
			var height = parent.Height;
			if ((parent.Left == node) == isInsertMode)
				if (parent.Bias == 2)
					if (parent.Left.Bias >= 0)
						parent = RotateR(parent);
					else
						parent = RotateLR(parent);
				else parent.Adjust();
			else
				if (parent.Bias == -2)
					if (parent.Right.Bias <= 0)
						parent = RotateL(parent);
					else
						parent = RotateRL(parent);
				else parent.Adjust();
			if (height == parent.Height) break;
			node = parent;
		}
	}
	public void Add(T item)
	{
		var parent = sentinel;
		var pos = sentinel.Left;
		var isLeft = true;
		count++;
		while (pos != sentinel)
			if (comp(item, pos.Item) < 0) { parent = pos; pos = pos.Left; isLeft = true; }
			else { parent = pos; pos = pos.Right; isLeft = false; }
		if (isLeft)
		{
			parent.Left = new AVLNode(item, parent, this);
			Adjust(true, parent.Left);
		}
		else
		{
			parent.Right = new AVLNode(item, parent, this);
			Adjust(true, parent.Right);
		}
	}
	// if equals(x,y) holds then !(comp(x,y)<0) and !(comp(x,y)>0) must hold
	// i.e. equals(x,y) -> comp(x,y)=0
	private bool Remove(T item, AVLNode start)
	{
		var pos = start;
		while (pos != sentinel)
		{
			if (comp(item, pos.Item) < 0) pos = pos.Left;
			else if (comp(item, pos.Item) > 0) pos = pos.Right;
			else if (equals(pos.Item, item))
			{
				if (pos.Left == sentinel)
				{
					Replace(pos, pos.Right);
					Adjust(false, pos.Right);
				}
				else
				{
					var max = Max(pos.Left);
					pos.Item = max.Item;
					Replace(max, max.Left);
					Adjust(false, max.Left);
				}
				count--;
				return true;
			}
			else return Remove(item, pos.Left) || Remove(item, pos.Right);
		}
		return false;
	}
	public bool Remove(T item) { return Remove(item, sentinel.Left); }
	private AVLNode Max(AVLNode node)
	{
		while (node.Right != sentinel) node = node.Right;
		return node;
	}
	private AVLNode Min(AVLNode node)
	{
		while (node.Left != sentinel) node = node.Left;
		return node;
	}
	public bool Contains(T item)
	{
		var pos = sentinel.Left;
		while (pos != sentinel)
		{
			if (comp(item, pos.Item) < 0) pos = pos.Left;
			else if (comp(item, pos.Item) > 0) pos = pos.Right;
			else return true;
		}
		return false;
	}
	public T Find(T item)
	{
		var pos = sentinel.Left;
		while (pos != sentinel)
		{
			if (comp(item, pos.Item) < 0) pos = pos.Left;
			else if (comp(item, pos.Item) > 0) pos = pos.Right;
			else return pos.Item;
		}
		return default(T);
	}
	public T Min() { return Min(sentinel.Left).Item; }
	public T Max() { return Max(sentinel.Left).Item; }
	public bool IsEmpty { get { return sentinel.Left == sentinel; } }
	public void Clear() { sentinel.Left = sentinel; count = 0; sentinel.ResetAsSentinel(); }
	public IEnumerator<T> GetEnumerator() { return sentinel.Left.GetEnumerator(); }
	IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
	public void CopyTo(T[] array, int arrayIndex) { foreach (var x in this) array[arrayIndex++] = x; }
	public int Count { get { return count; } }
	public bool IsReadOnly { get { return true; } }
	public void CopyTo(Array array, int index) { foreach (var x in this) array.SetValue(x, index++); }
	public bool IsSynchronized { get { return false; } }
	public object SyncRoot { get { return null; } }
	public override string ToString()
	{
		var nodes = new StringBuilder();
		var edges = new StringBuilder();
		ConcatSubTree(nodes, edges, sentinel.Left, "L");
		return "digraph G {\n" + nodes.ToString() + edges.ToString() + "}";
	}
	private void ConcatSubTree(StringBuilder nodes, StringBuilder edges, AVLNode node, string code)
	{
		if (node == sentinel) return;
		nodes.Append("\tv" + code + " [label = \"" + node.Height + ":" + node.Item + "\"];\n");
		if (node.Left != sentinel) edges.Append("\tv" + code + " -> v" + code + "L;\n");
		if (node.Right != sentinel) edges.Append("\tv" + code + " -> v" + code + "R;\n");
		ConcatSubTree(nodes, edges, node.Left, code + "L");
		ConcatSubTree(nodes, edges, node.Right, code + "R");
	}
	public bool IsBalanced() { return IsBalanced(sentinel.Left); }
	public bool IsValidBinarySearchTree() { return IsValidBinarySearchTree(sentinel.Left); }
	private bool IsBalanced(AVLNode node) { return node == sentinel || (Math.Abs(node.Bias) < 2 && IsBalanced(node.Left) && IsBalanced(node.Right)); }
	private bool IsValidBinarySearchTree(AVLNode node)
	{
		return node == sentinel || (Small(node.Item, node.Left) && Large(node.Item, node.Right)
			&& IsValidBinarySearchTree(node.Left) && IsValidBinarySearchTree(node.Right));
	}
	private bool Small(T item, AVLNode node) { return node == sentinel || (comp(item, node.Item) >= 0 && Small(item, node.Left) && Small(item, node.Right)); }
	private bool Large(T item, AVLNode node) { return node == sentinel || (comp(item, node.Item) <= 0 && Large(item, node.Left) && Large(item, node.Right)); }
	public static void CheckAVL(Random rand, int N)
	{
		Comparison<double> comp = (x, y) => x.CompareTo(y);
		var avl = new AVLTree<double>(comp);
		var toBeLeft = new double[N];
		var toBeRemoved = new double[N];
		for (var i = 0; i < N; i++) avl.Add(toBeRemoved[i] = rand.NextDouble());
		for (var i = 0; i < N; i++) avl.Add(toBeLeft[i] = rand.NextDouble());
		for (var i = 0; i < N; i++) Console.Write(avl.Remove(toBeRemoved[i]) ? "" : "!!!NOT REMOVED!!! => " + toBeRemoved[i] + "\n");
		var insertErrors = toBeLeft.All(x => avl.Contains(x));
		var deleteErrors = avl.Count == N;
		//Console.WriteLine("【AVL木の構造】");
		//Console.WriteLine(avl);
		if (insertErrors && deleteErrors) Console.WriteLine("○\t挿入, 削除操作が正しく行われています.");
		else if (insertErrors) Console.WriteLine("×\t挿入(または削除)操作に問題があります.");
		else Console.WriteLine("×\t削除(または挿入)操作に問題があります.");
		if (avl.IsBalanced()) Console.WriteLine("○\tAVL木は平衡条件を保っています.");
		else Console.WriteLine("×\tAVL木の平衡条件が破れています.");
		if (avl.IsValidBinarySearchTree()) Console.WriteLine("○\tAVL木は二分探索木になっています.");
		else Console.WriteLine("×\tAVL木は二分探索木になっていません.");
		Array.Sort(toBeLeft, comp);
		Console.WriteLine("最小値 : " + avl.Min() + " ≡ " + toBeLeft.First());
		Console.WriteLine("最大値 : " + avl.Max() + " ≡ " + toBeLeft.Last());
		Console.WriteLine("要素数 : " + avl.Count + "個");
	}
}
class PriorityQueue<T> : IEnumerable<T>, ICollection, IEnumerable
{
	private Comparison<T> comp;
	private List<T> list;
	private int count;
	public int Count { get { return count; } }
	public bool IsEmpty { get { return count == 0; } }
	public PriorityQueue(Comparison<T> comparison)
	{
		comp = comparison;
		list = new List<T>();
		count = 0;
	}
	public PriorityQueue(Comparison<T> comparison, IEnumerable<T> source) : this(comparison) { foreach (var x in source) Enqueue(x); }
	public PriorityQueue(Comparison<T> comparison, int capacity) : this(comparison) { list.Capacity = capacity; }
	/// <summary>
	/// add an item
	/// this is an O(log n) operation
	/// </summary>
	/// <param name="x">item</param>
	public void Enqueue(T x)
	{
		var pos = count++;
		list.Add(x);
		while (pos > 0)
		{
			var p = (pos - 1) / 2;
			if (comp(list[p], x) <= 0) break;
			list[pos] = list[p];
			pos = p;
		}
		list[pos] = x;
	}
	/// <summary>
	/// return the minimum element and remove it
	/// this is an O(log n) operation
	/// </summary>
	/// <returns>the minimum</returns>
	public T Dequeue()
	{
		if (count == 0) throw new InvalidOperationException();
		var value = list[0];
		var x = list[--count];
		list.RemoveAt(count);
		if (count == 0) return value;
		var pos = 0;
		while (pos * 2 + 1 < count)
		{
			var a = 2 * pos + 1;
			var b = 2 * pos + 2;
			if (b < count && comp(list[b], list[a]) < 0) a = b;
			if (comp(list[a], x) >= 0) break;
			list[pos] = list[a];
			pos = a;
		}
		list[pos] = x;
		return value;
	}
	/// <summary>
	/// look at the minimum element
	/// this is an O(1) operation
	/// </summary>
	/// <returns>the minimum</returns>
	public T Peek() { return list[0]; }
	/// <summary>
	/// clear all elements
	/// this is an O(1) operation
	/// </summary>
	public void Clear() { list = new List<T>(); count = 0; }
	/// <summary>
	/// Sets the capacity to count, if count is less than a threshold value.
	/// this is an O(1) operation
	/// </summary>
	public void TrimExcess() { list.TrimExcess(); }
	/// <summary>
	/// check whether item is in this queue
	/// this is an O(n) operation
	/// </summary>
	public bool Contains(T item) { return list.Contains(item); }
	void CopyTo(Array array, int index)
	{
		var tmp = new PriorityQueue<T>(comp, list.Count);
		for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
		while (!tmp.IsEmpty) array.SetValue(tmp.Dequeue(), index++);
	}
	bool ICollection.IsSynchronized { get { return false; } }
	object ICollection.SyncRoot { get { return null; } }
	public IEnumerator<T> GetEnumerator()
	{
		var tmp = new PriorityQueue<T>(comp, list.Count);
		for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
		while (!tmp.IsEmpty) yield return tmp.Dequeue();
	}
	IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
	void ICollection.CopyTo(Array array, int index) { CopyTo(array, index); }
	int ICollection.Count { get { return count; } }
	public bool Any() { return count > 0; }
}
class PairComparer<S, T> : IComparer<Pair<S, T>>
	where S : IComparable<S>
	where T : IComparable<T>
{
	public PairComparer() { }
	public int Compare(Pair<S, T> x, Pair<S, T> y)
	{
		var p = x.First.CompareTo(y.First);
		if (p != 0) return p;
		else return x.Second.CompareTo(y.Second);
	}
}
class Pair<S, T>
{
	public S First;
	public T Second;
	public Pair() { First = default(S); Second = default(T); }
	public Pair(S s, T t) { First = s; Second = t; }
	public override string ToString() { return "(" + First + ", " + Second + ")"; }
	public override int GetHashCode() { return First.GetHashCode() ^ Second.GetHashCode(); }
	public override bool Equals(object obj)
	{
		if (ReferenceEquals(this, obj)) return true;
		else if (obj == null) return false;
		var tmp = obj as Pair<S, T>;
		return (object)tmp != null && First.Equals(tmp.First) && Second.Equals(tmp.Second);
	}
}
class Point : Pair<int, int>
{
	public int X { get { return First; } set { First = value; } }
	public int Y { get { return Second; } set { Second = value; } }
	public Point() : base(0, 0) { }
	public Point(int x, int y) : base(x, y) { }
	public IEnumerable<Point> Neighbors4()
	{
		yield return new Point(X - 1, Y);
		yield return new Point(X, Y - 1);
		yield return new Point(X, Y + 1);
		yield return new Point(X + 1, Y);
	}
	public IEnumerable<Point> Neighbors8()
	{
		yield return new Point(X - 1, Y - 1);
		yield return new Point(X - 1, Y);
		yield return new Point(X - 1, Y + 1);
		yield return new Point(X, Y - 1);
		yield return new Point(X, Y + 1);
		yield return new Point(X + 1, Y - 1);
		yield return new Point(X + 1, Y);
		yield return new Point(X + 1, Y + 1);
	}
}
class Printer : IDisposable
{
	private TextWriter file;
	public Printer() { file = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; }
	public void Write(string value) { file.Write(value); }
	public void Write<T>(T value) { file.Write(value); }
	public void Write(string str, params object[] args) { file.Write(str, args); }
	public void WriteLine() { file.WriteLine(); }
	public void WriteLine(string value) { file.WriteLine(value); }
	public void WriteLine<T>(T value) { file.WriteLine(value); }
	public void WriteLine(string str, params object[] args) { file.WriteLine(str, args); }
	public void Dispose() { file.Flush(); }
}
class Scan : IDisposable
{
	private TextReader file;
	public Scan(bool useConsole) { file = useConsole ? Console.In : new StreamReader("input.txt"); }
	public void Dispose() { if (file != Console.In)  file.Dispose(); }
	public int ReadInt() { return int.Parse(file.ReadLine()); }
	public uint ReadUInt() { return uint.Parse(file.ReadLine()); }
	public long ReadLong() { return long.Parse(file.ReadLine()); }
	public double ReadDouble() { return double.Parse(file.ReadLine()); }
	public decimal ReadDecimal() { return decimal.Parse(file.ReadLine()); }
	public string ReadString() { return file.ReadLine(); }
	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> ReadTuple<S>() { S s; Read(out s); return new Tuple<S>(s); }
	public Tuple<S, T> ReadTuple<S, T>() { S s; T t; Read(out s, out t); return new Tuple<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 Tuple<S, T, U, V> ReadTuple<S, T, U, V>() { S s; T t; U u; V v; Read(out s, out t, out u, out v); return new Tuple<S, T, U, V>(s, t, u, v); }
	public Point ReadPoint() { int s, t; Read(out s, out t); return new Point(s, t); }
	public void Read<S>(out S s)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S))).ToArray();
		s = (S)read[0];
	}
	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];
	}
	public void Read<S, T, U, V>(out S s, out T t, out U u, out V v)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U)), Type.GetTypeCode(typeof(V))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
		u = (U)read[2];
		v = (V)read[3];
	}
	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();
		}
	}
	public T[,] ReadBoard<T>(int X, int Y, Func<char, int, int, T> selector)
	{
		var array = new T[X, Y];
		for (var y = 0; y < Y; y++)
		{
			var str = ReadString();
			for (var x = 0; x < X; x++) array[x, y] = selector(str[x], x, y);
		}
		return array;
	}
}
static class Func
{
	public static readonly int Inf = 1073741789;	// 2 * Inf < int.MaxValue, and Inf is a prime number
	/// <summary>
	/// Find the first number x such that pred(x) is true
	/// if pred(x) is false for all min&lt;=x&lt;max, then return max
	/// in other words, pred(max) is assumed to be true
	/// </summary>
	/// <param name="min">inclusive lower limit</param>
	/// <param name="max">exclusive upper limit</param>
	/// <param name="pred">monotonous predicate, i.e. if pred(a) and a&lt;b, then pred(b)</param>
	/// <returns>first number such that satisfy pred</returns>
	public static long FirstBinary(long min, long max, Predicate<long> pred)
	{
		var left = min;
		var right = max;
		while (left < right)
		{
			var mid = (left + right) >> 1;
			if (pred(mid)) right = mid;
			else left = mid + 1;
		}
		return left;
	}
	public static void Swap<T>(this IList<T> array, int i, int j) { var tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
	public static T IndexAt<T>(this T[,] array, Pair<int, int> index) { return array[index.First, index.Second]; }
	public static bool InRegion(this Pair<int, int> p, int X, int Y) { return p.InRegion(0, X, 0, Y); }
	public static bool InRegion(this Pair<int, int> p, int x, int X, int y, int Y) { return p.First >= x && p.Second >= y && p.First < X && p.Second < Y; }
	/// <summary>
	/// get all permutation of 0, 1, ..., n - 1
	/// </summary>
	/// <param name="n">length of array</param>
	/// <param name="func">if you want to change the elements of the array, you must take a copy</param>
	public static void Permutation(int n, Action<int[]> func)
	{
		var array = new int[n];
		var unused = new bool[n];
		for (var i = 0; i < n; i++) unused[i] = true;
		Permutation(n, 0, array, unused, func);
	}
	private static void Permutation(int n, int i, int[] array, bool[] unused, Action<int[]> func)
	{
		if (i == n) func(array);
		else
			for (var x = 0; x < n; x++)
				if (unused[x])
				{
					array[i] = x;
					unused[x] = false;
					Permutation(n, i + 1, array, unused, func);
					unused[x] = true;
				}
	}
	public static long Fact(int n)
	{
		var fact = 1L;
		for (var i = 2; i <= n; i++) fact *= i;
		return fact;
	}
	public static long LCM(long n, long m) { return Math.Abs((n / GCD(n, m)) * m); }
	public static long Divide(long n, long m) { return (n - Remainder(n, m)) / m; }
	public static long Remainder(long n, long m)
	{
		if (m == 0) throw new DivideByZeroException();
		else if (m < 0) return Remainder(n, -m);
		else
		{
			var r = n % m;
			return r < 0 ? r + m : r;
		}
	}
	public static long GCD(long n, long m)
	{
		var a = Math.Abs(n);
		var b = Math.Abs(m);
		if (a < b) { var c = a; a = b; b = c; }
		while (b > 0)
		{
			var c = a % b;
			a = b;
			b = c;
		}
		return a;
	}
	public static decimal MeasureTime(Action action)
	{
		var sw = new System.Diagnostics.Stopwatch();
		sw.Restart();
		action();
		sw.Stop();
		return sw.ElapsedTicks * 1000m / System.Diagnostics.Stopwatch.Frequency;
	}
	public static int MaxElement<T>(this IEnumerable<T> source, Comparison<T> comp)
	{
		var p = source.GetEnumerator();
		if (!p.MoveNext()) return -1;
		var max = p.Current;
		var mi = 0;
		var i = 0;
		while (p.MoveNext())
		{
			i++;
			if (comp(max, p.Current) < 0)
			{
				max = p.Current;
				mi = i;
			}
		}
		return mi;
	}
	public static int MaxElement<T>(this IEnumerable<T> source) where T : IComparable<T> { return source.MaxElement((x, y) => x.CompareTo(y)); }
	public static int MinElement<T>(IEnumerable<T> source, Comparison<T> comp) { return source.MaxElement((x, y) => comp(y, x)); }
	public static int MinElement<T>(IEnumerable<T> source) where T : IComparable<T> { return source.MaxElement((x, y) => y.CompareTo(x)); }
	public static void Shuffle<T>(IList<T> source, Random rand) { for (var i = source.Count - 1; i >= 0; --i) source.Swap(i, rand.Next(0, i + 1)); }
	public static char NextChar(this Random rand) { return (char)(rand.Next(0, 'z' - 'a' + 1) + 'a'); }
	public static string NextString(this Random rand, int length) { return new string(Enumerable.Range(0, length).Select(_ => rand.NextChar()).ToArray()); }
	public static IEnumerable<T> Rotate<T>(this IEnumerable<T> source)
	{
		var e = source.GetEnumerator();
		if (e.MoveNext())
		{
			var f = e.Current;
			while (e.MoveNext()) yield return e.Current;
			yield return f;
		}
	}
	public static T Apply<T>(this Func<T, T> func, T x, int n)
	{
		var a = x;
		for (int i = 0; i < n; i++) a = func(a);
		return a;
	}
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User selpo
Language C# (Mono 3.2.1.0)
Score 0
Code Size 36498 Byte
Status
Exec Time 2050 ms
Memory 110440 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 0 / 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 172 ms 11408 KB
subtask0_sample_02.txt 172 ms 11412 KB
subtask0_sample_03.txt 176 ms 11420 KB
subtask1_01.txt 168 ms 11292 KB
subtask1_02.txt 184 ms 12736 KB
subtask1_03.txt 2048 ms 105812 KB
subtask1_04.txt 2049 ms 105944 KB
subtask1_05.txt 2049 ms 105912 KB
subtask1_06.txt 2050 ms 110440 KB
subtask1_07.txt 2048 ms 105952 KB
subtask1_08.txt 2045 ms 105960 KB
subtask1_09.txt 2049 ms 106228 KB
subtask1_10.txt 2047 ms 105980 KB
subtask1_11.txt 183 ms 12724 KB
subtask1_12.txt 187 ms 12712 KB
subtask1_13.txt 2050 ms 105860 KB
subtask1_14.txt 2048 ms 105852 KB
subtask1_15.txt 576 ms 25224 KB
subtask1_16.txt 580 ms 25232 KB
subtask1_17.txt 573 ms 25228 KB
subtask1_18.txt 577 ms 25236 KB
subtask1_19.txt 572 ms 25236 KB
subtask1_20.txt 575 ms 25228 KB
subtask1_21.txt 574 ms 25228 KB
subtask1_22.txt 580 ms 25276 KB
subtask1_23.txt 571 ms 25268 KB
subtask1_24.txt 573 ms 25236 KB