Submission #3003402


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
map<int,ll>mp;
int d[123456];
vector<pii>g[123456];
void dfs(int s){
    for(auto &x:g[s]){
        if(d[x.first]==-1){
            d[x.first] = d[s]^x.second;
            dfs(x.first);
        }
    }
}
int main(){
    int n,x;
    cin >> n >> x;
    rep(i,n-1){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        g[a].push_back(pii(b,c));
        g[b].push_back(pii(a,c));
    }
    memset(d,-1,sizeof(d));
    d[0] = 0;
    dfs(0);
    rep(i,n){
        mp[d[i]]++;
    }
    ll ans = 0;
    for(auto &y:mp){
        if(y.first!=(y.first^x))ans += mp[y.first^x]*y.second;
        else ans+=y.second*(y.second-1);
    }
    cout << ans/2 << endl;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User polyomino
Language C++14 (Clang 3.8.0)
Score 100
Code Size 1311 Byte
Status AC
Exec Time 348 ms
Memory 19712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 27
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 3584 KB
subtask0_sample_02.txt AC 3 ms 3584 KB
subtask0_sample_03.txt AC 3 ms 3584 KB
subtask1_01.txt AC 3 ms 3584 KB
subtask1_02.txt AC 4 ms 3712 KB
subtask1_03.txt AC 338 ms 19712 KB
subtask1_04.txt AC 348 ms 19712 KB
subtask1_05.txt AC 339 ms 19712 KB
subtask1_06.txt AC 212 ms 9856 KB
subtask1_07.txt AC 230 ms 7296 KB
subtask1_08.txt AC 232 ms 7296 KB
subtask1_09.txt AC 264 ms 8320 KB
subtask1_10.txt AC 265 ms 8320 KB
subtask1_11.txt AC 4 ms 3712 KB
subtask1_12.txt AC 4 ms 3712 KB
subtask1_13.txt AC 246 ms 7296 KB
subtask1_14.txt AC 246 ms 7296 KB
subtask1_15.txt AC 28 ms 4736 KB
subtask1_16.txt AC 28 ms 4736 KB
subtask1_17.txt AC 28 ms 4736 KB
subtask1_18.txt AC 28 ms 4736 KB
subtask1_19.txt AC 28 ms 4736 KB
subtask1_20.txt AC 28 ms 4736 KB
subtask1_21.txt AC 28 ms 4736 KB
subtask1_22.txt AC 28 ms 4736 KB
subtask1_23.txt AC 28 ms 4736 KB
subtask1_24.txt AC 28 ms 4736 KB