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

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 2015-10-13 01:49:43+0900 C - エックスオア多橋君 okaduki C++11 (GCC 4.9.2) 100 1652 Byte AC 221 ms 17632 KB

#### Test Cases

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