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 |
|
|
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 |