Submission #1113728
Source Code Expand
#include <bits/stdc++.h> #define ll long long using namespace std; const ll size = 100000; ll N, X; ll x[size], y[size], c[size]; vector< pair<ll, ll> > edges[size]; void init() { cin >> N >> X; for(ll i = 0; i < N - 1; i++) { cin >> x[i] >> y[i] >> c[i]; x[i] -= 1; y[i] -= 1; edges[ x[i] ].push_back(make_pair(y[i], c[i])); edges[ y[i] ].push_back(make_pair(x[i], c[i])); } } bool visited[size]; unordered_map<ll, ll> hashMap; void makeHashMap() { queue< pair<ll, ll> > q; q.push(make_pair(0, 0)); hashMap[0] += 1ll; visited[0] = true; while(q.size()) { pair<ll, ll> qfront = q.front(); q.pop(); ll from = qfront.first; ll prevxor = qfront.second; for(pair<ll, ll> path: edges[from]) { if(visited[path.first] == false) { visited[path.first] = true; ll newxor = prevxor ^ path.second; q.push( make_pair(path.first, newxor) ); hashMap[newxor] += 1ll; } } } } void solve() { makeHashMap(); ll ans = 0; for(pair<ll, ll> p: hashMap) { if(p.first == (p.first ^ X) ) { ans += p.second * hashMap[p.first ^ X] * 2ll; }else { ans += p.second * hashMap[p.first ^ X]; } } cout << ans / 2ll << endl; } int main() { init(); solve(); }
Submission Info
Submission Time | |
---|---|
Task | C - エックスオア多橋君 |
User | kkty |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1358 Byte |
Status | WA |
Exec Time | 149 ms |
Memory | 17060 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
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 | 4224 KB |
subtask0_sample_02.txt | AC | 2 ms | 4224 KB |
subtask0_sample_03.txt | AC | 3 ms | 4224 KB |
subtask1_01.txt | WA | 3 ms | 4224 KB |
subtask1_02.txt | WA | 3 ms | 4224 KB |
subtask1_03.txt | WA | 142 ms | 17060 KB |
subtask1_04.txt | WA | 149 ms | 17060 KB |
subtask1_05.txt | WA | 144 ms | 17060 KB |
subtask1_06.txt | WA | 88 ms | 9728 KB |
subtask1_07.txt | AC | 96 ms | 10112 KB |
subtask1_08.txt | AC | 95 ms | 10112 KB |
subtask1_09.txt | AC | 107 ms | 11008 KB |
subtask1_10.txt | AC | 107 ms | 11008 KB |
subtask1_11.txt | AC | 3 ms | 4352 KB |
subtask1_12.txt | AC | 3 ms | 4352 KB |
subtask1_13.txt | AC | 102 ms | 10240 KB |
subtask1_14.txt | AC | 101 ms | 10112 KB |
subtask1_15.txt | WA | 13 ms | 5120 KB |
subtask1_16.txt | WA | 13 ms | 5120 KB |
subtask1_17.txt | WA | 13 ms | 5120 KB |
subtask1_18.txt | WA | 13 ms | 5120 KB |
subtask1_19.txt | WA | 13 ms | 5120 KB |
subtask1_20.txt | WA | 13 ms | 5120 KB |
subtask1_21.txt | WA | 13 ms | 5120 KB |
subtask1_22.txt | WA | 13 ms | 5120 KB |
subtask1_23.txt | WA | 13 ms | 5120 KB |
subtask1_24.txt | WA | 13 ms | 5120 KB |