Submission #1519842


Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;

struct edge{ int to,cost; };

vector<edge> G[100000];
vector<int> ord;
int cnt = 0,l[100000],r[100000],d[200000];

void dfs(int v,int prev,int pc){
	l[v] = cnt;
	ord.push_back(v);
	for(edge e : G[v]){
		if(e.to == prev) continue;
		d[++cnt] = e.cost;
		dfs(e.to,v,e.cost);
	}
	d[++cnt] = pc;
	r[v] = cnt;
}

signed main(){
	int n,x;
	cin >> n >> x;
	for(int i = 0;i < n - 1;i++){
		int a,b,c;
		cin >> a >> b >> c; a--;b--;
		G[a].push_back({b,c});
		G[b].push_back({a,c});
	}
	dfs(0,-1,0);
	unordered_map<int,int> mp;
	int pos = 0,ans = 0;
	for(int i = 1;i < cnt;i++) d[i] ^= d[i - 1];
	for(int i = 0;i < n;i++) d[r[i]] = -1;
	for(int i : ord){
		while(pos < l[i]) mp[d[pos++]]++;
		ans += mp[x ^ d[l[i]]];
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User hoget157
Language C++14 (GCC 5.4.1)
Score 100
Code Size 896 Byte
Status AC
Exec Time 155 ms
Memory 19868 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 27
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 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 AC 3 ms 3840 KB
subtask0_sample_02.txt AC 2 ms 3712 KB
subtask0_sample_03.txt AC 2 ms 3712 KB
subtask1_01.txt AC 2 ms 3712 KB
subtask1_02.txt AC 3 ms 3712 KB
subtask1_03.txt AC 153 ms 19864 KB
subtask1_04.txt AC 155 ms 19868 KB
subtask1_05.txt AC 153 ms 19868 KB
subtask1_06.txt AC 93 ms 17524 KB
subtask1_07.txt AC 105 ms 11768 KB
subtask1_08.txt AC 103 ms 11764 KB
subtask1_09.txt AC 116 ms 12408 KB
subtask1_10.txt AC 112 ms 12404 KB
subtask1_11.txt AC 3 ms 3712 KB
subtask1_12.txt AC 3 ms 3712 KB
subtask1_13.txt AC 107 ms 11764 KB
subtask1_14.txt AC 107 ms 11768 KB
subtask1_15.txt AC 13 ms 4992 KB
subtask1_16.txt AC 13 ms 4992 KB
subtask1_17.txt AC 13 ms 4992 KB
subtask1_18.txt AC 13 ms 4992 KB
subtask1_19.txt AC 13 ms 4992 KB
subtask1_20.txt AC 13 ms 4992 KB
subtask1_21.txt AC 14 ms 4992 KB
subtask1_22.txt AC 13 ms 4992 KB
subtask1_23.txt AC 13 ms 4992 KB
subtask1_24.txt AC 13 ms 4992 KB