Submission #524564


Source Code Expand

Copy
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int root=0;
		parent=new int[N];
		XX=new int[N];
		bfs(root,0);
//Console.WriteLine(String.Join(" ",XX));		
//Console.WriteLine(String.Join(" ",parent));		
		Dictionary<int,long> DD=new Dictionary<int,long>();
		for(int i=0;i<N;i++){
			if(DD.ContainsKey(XX[i])==false)DD.Add(XX[i],0);
			DD[XX[i]]+=1;
		}
		
		long ans=0;
		HashSet<int> H=new HashSet<int>();
		foreach(var k in DD.Keys){
			if(H.Contains(k))continue;
			H.Add(k);
			if(DD.ContainsKey(k^X) && (k^X)!=k){
				H.Add(k^X);
				ans+=DD[k]*DD[k^X];
				continue;
			}
			if(DD.ContainsKey(k^X) && (k^X)==k){
				H.Add(k^X);
				ans+=DD[k]*(DD[k^X]-1)/2;
				continue;
			}
		}
		
		Console.WriteLine(ans);
		
	}
	int N,X;
	List<Pair>[] E;
	int[] parent;
	int[] XX;
	void dfs(int now, int par,int x){
		parent[now]=par;
		XX[now]=x;
		foreach(var v in E[now]){
			if(v.Pos!=par){
				dfs(v.Pos,now,x^v.Cost);
			}
		}
	}
	
	void bfs(int strt,int x_strt){
		Queue<int> Q=new Queue<int>();
		parent[strt]=-1;XX[strt]=x_strt;
		Q.Enqueue(strt);
		while(Q.Count>0){
			int now=Q.Dequeue();
			int par=parent[now];
			foreach(var v in E[now]){
				if(v.Pos!=par){
					parent[v.Pos]=now;XX[v.Pos]=XX[now]^v.Cost;
					Q.Enqueue(v.Pos);
				}
			}
		}
	}
	
	
	
	public Sol(){
		var d=ria();
		N=d[0];X=d[1];
		E=new List<Pair>[N];
		for(int i=0;i<N;i++)E[i]=new List<Pair>();
		for(int i=0;i<N-1;i++){
			var dd=ria();
			E[dd[0]-1].Add(new Pair(dd[1]-1,dd[2]));
			E[dd[1]-1].Add(new Pair(dd[0]-1,dd[2]));
		}
	}

	class Pair{
		public int Pos;
		public int Cost;
		public Pair(int pos,int cost){
			Pos=pos;Cost=cost;
		}	
	}


	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User kuuso
Language C# (Mono 3.2.1.0)
Score 100
Code Size 2504 Byte
Status
Exec Time 643 ms
Memory 45204 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 171 ms 11104 KB
subtask0_sample_02.txt 165 ms 11080 KB
subtask0_sample_03.txt 164 ms 11180 KB
subtask1_01.txt 165 ms 11052 KB
subtask1_02.txt 168 ms 11644 KB
subtask1_03.txt 632 ms 45056 KB
subtask1_04.txt 643 ms 45108 KB
subtask1_05.txt 641 ms 45204 KB
subtask1_06.txt 416 ms 34612 KB
subtask1_07.txt 542 ms 34852 KB
subtask1_08.txt 552 ms 34732 KB
subtask1_09.txt 566 ms 36820 KB
subtask1_10.txt 577 ms 36788 KB
subtask1_11.txt 177 ms 11620 KB
subtask1_12.txt 173 ms 11616 KB
subtask1_13.txt 557 ms 34860 KB
subtask1_14.txt 532 ms 34864 KB
subtask1_15.txt 211 ms 17800 KB
subtask1_16.txt 208 ms 17800 KB
subtask1_17.txt 210 ms 17880 KB
subtask1_18.txt 207 ms 17824 KB
subtask1_19.txt 211 ms 17748 KB
subtask1_20.txt 210 ms 17848 KB
subtask1_21.txt 223 ms 17796 KB
subtask1_22.txt 217 ms 17792 KB
subtask1_23.txt 210 ms 17752 KB
subtask1_24.txt 211 ms 17832 KB