Submission #526236


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

struct E{
  int to, c;
  E(int to_, int c_): to(to_), c(c_){
  }
};


LL dfs(int X, int u, VI& dist, vector<vector<E>>& G, map<int,LL>& memo){
  LL res = 0;
  for(E& e: G[u]){
	if(dist[e.to] >= 0) continue;
	int d = dist[u] ^ e.c;
	if(memo.count(X^d))
	  res += memo[X^d];
	dist[e.to] = d;
	memo[d]++;
	res += dfs(X, e.to, dist, G, memo);
  }

  return res;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, X; cin >> N >> X;
  vector<vector<E>> G(N);
  REP(i,N-1){
	int a, b, c; cin >> a >> b >> c;
	--a, --b;
	G[a].PB(E(b,c));
	G[b].PB(E(a,c));
  }

  VI dist(N, -1);
  map<int,LL> memo;
  dist[0] = 0;
  memo[0]++;
  LL ans = dfs(X, 0, dist, G, memo);
  cout << ans << endl;
  
  return 0;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User okaduki
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1652 Byte
Status
Exec Time 221 ms
Memory 17632 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 28 ms 860 KB
subtask0_sample_02.txt 26 ms 912 KB
subtask0_sample_03.txt 27 ms 916 KB
subtask1_01.txt 27 ms 912 KB
subtask1_02.txt 28 ms 912 KB
subtask1_03.txt 221 ms 13536 KB
subtask1_04.txt 220 ms 13400 KB
subtask1_05.txt 221 ms 13540 KB
subtask1_06.txt 110 ms 17632 KB
subtask1_07.txt 114 ms 7264 KB
subtask1_08.txt 115 ms 7292 KB
subtask1_09.txt 178 ms 8284 KB
subtask1_10.txt 179 ms 8284 KB
subtask1_11.txt 28 ms 860 KB
subtask1_12.txt 28 ms 880 KB
subtask1_13.txt 140 ms 7268 KB
subtask1_14.txt 145 ms 7284 KB
subtask1_15.txt 42 ms 1892 KB
subtask1_16.txt 41 ms 1888 KB
subtask1_17.txt 42 ms 1884 KB
subtask1_18.txt 41 ms 1892 KB
subtask1_19.txt 42 ms 1888 KB
subtask1_20.txt 43 ms 1880 KB
subtask1_21.txt 42 ms 1880 KB
subtask1_22.txt 42 ms 1884 KB
subtask1_23.txt 40 ms 1888 KB
subtask1_24.txt 44 ms 1896 KB