Submission #1499617


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = long long;

map<int, ll> dfs(int v, int prev, int const X, vector<vector<pii>> const& T, ll& res) {
    map<int, ll> ret;
    ret[0] = 1;
    for(auto& p : T[v]) {
        int to = p.first, cost = p.second;
        if(to == prev) {
            continue;
        }
        auto t = dfs(to, v, X, T, res);
        vector<pii> u;
        for(auto& q : t) {
            int x = q.first ^ cost ^ X;
            if(ret.count(x) != 0) {
                res += ret[x] * q.second;
            }
            u.emplace_back(q.first ^ cost, q.second);
        }
        for(auto&& q : move(u)) {
            ret[q.first] += q.second;
        }
    }
    return ret;
}

int main() {
    int N, X;
    cin >> N >> X;
    vector<vector<pii>> T(N);
    for(int i = 0; i < N - 1; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        T[x].emplace_back(y, c);
        T[y].emplace_back(x, c);
    }

    ll res = 0;
    dfs(0, -1, X, T, res);
    cout << res << endl;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User Suibaka
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1112 Byte
Status TLE
Exec Time 2104 ms
Memory 35456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 25
TLE × 2
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 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 2 ms 256 KB
subtask1_03.txt TLE 2104 ms 19228 KB
subtask1_04.txt TLE 2104 ms 19784 KB
subtask1_05.txt AC 1908 ms 19780 KB
subtask1_06.txt AC 108 ms 35456 KB
subtask1_07.txt AC 158 ms 6400 KB
subtask1_08.txt AC 153 ms 6400 KB
subtask1_09.txt AC 1154 ms 10320 KB
subtask1_10.txt AC 1249 ms 9080 KB
subtask1_11.txt AC 2 ms 384 KB
subtask1_12.txt AC 2 ms 384 KB
subtask1_13.txt AC 486 ms 7232 KB
subtask1_14.txt AC 477 ms 7404 KB
subtask1_15.txt AC 72 ms 1896 KB
subtask1_16.txt AC 83 ms 1920 KB
subtask1_17.txt AC 106 ms 1920 KB
subtask1_18.txt AC 117 ms 1920 KB
subtask1_19.txt AC 95 ms 1920 KB
subtask1_20.txt AC 109 ms 1920 KB
subtask1_21.txt AC 125 ms 1920 KB
subtask1_22.txt AC 91 ms 1920 KB
subtask1_23.txt AC 75 ms 1832 KB
subtask1_24.txt AC 115 ms 1924 KB