Submission #523919


Source Code Expand

Copy
#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

map<ll, ll> c;
vector<pair<ll, ll>> G[101010];
ll dp[101010];

void dfs(int curr, int prev) {
	c[dp[curr]]++;
	for (auto e : G[curr]) if (e.first != prev) {
		int next = e.first;
		dp[next] = dp[curr] ^ e.second;
		dfs(next, curr);
	}
}

int main() {
	ll N, X;
	cin >> N >> X;	
	rep (i, N - 1) {
		ll x, y, c;
		cin >> x >> y >> c;
		x--; y--;
		G[x].emplace_back(y, c);
		G[y].emplace_back(x, c);
	}
	dfs(0, -1);
	ll ans = 0;
	rep (i, N) {
		if ((X ^ dp[i]) == dp[i]) {
			ans--;
		}
		ans += c[X ^ dp[i]];
	}
	ans /= 2;
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User xumpei
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1132 Byte
Status
Exec Time 434 ms
Memory 21416 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 30 ms 3228 KB
subtask0_sample_02.txt 32 ms 3116 KB
subtask0_sample_03.txt 32 ms 3224 KB
subtask1_01.txt 32 ms 3108 KB
subtask1_02.txt 31 ms 3232 KB
subtask1_03.txt 418 ms 21416 KB
subtask1_04.txt 408 ms 21412 KB
subtask1_05.txt 434 ms 21412 KB
subtask1_06.txt 199 ms 13212 KB
subtask1_07.txt 219 ms 8992 KB
subtask1_08.txt 209 ms 8984 KB
subtask1_09.txt 284 ms 10016 KB
subtask1_10.txt 278 ms 10012 KB
subtask1_11.txt 32 ms 3180 KB
subtask1_12.txt 33 ms 3168 KB
subtask1_13.txt 251 ms 8988 KB
subtask1_14.txt 256 ms 8996 KB
subtask1_15.txt 56 ms 4384 KB
subtask1_16.txt 57 ms 4384 KB
subtask1_17.txt 56 ms 4388 KB
subtask1_18.txt 56 ms 4384 KB
subtask1_19.txt 56 ms 4376 KB
subtask1_20.txt 55 ms 4380 KB
subtask1_21.txt 58 ms 4388 KB
subtask1_22.txt 55 ms 4388 KB
subtask1_23.txt 53 ms 4384 KB
subtask1_24.txt 52 ms 4452 KB