Submission #1161094


Source Code Expand

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<class graph_type> int compute_subtree_size(const graph_type &graph,const vector<bool> &centroid,vector<int> &subtree_size,int u,int p){
    int c=1;
    for(const auto &edge:graph[u]){
        int v=edge.to;
        if(v==p or centroid[v]) continue;
        c+=compute_subtree_size(graph,centroid,subtree_size,v,u);
    }
    subtree_size[u]=c;
    return c;
}

//tは連結成分全体のサイズ
//u以下で,削除により残る最大の部分木の頂点数が最小となる頂点の,(残る最大の部分木の頂点数,頂点番号)のペアを返す
template<class graph_type> pair<int,int> search_centroid(const graph_type &graph,const vector<bool> &centroid,const vector<int> &subtree_size,int u,int p,int t){
    pair<int,int> res=make_pair(inf,-1);
    int s=1,m=0;
    for(const auto &edge:graph[u]){
        int v=edge.to;
        if(v==p or centroid[v]) continue;
        res=min(res,search_centroid(graph,centroid,subtree_size,v,u,t));
        m=max(m,subtree_size[v]);
        s+=subtree_size[v];
    }
    m=max(m,t-s);
    res=min(res,make_pair(m,u));
    return res;
}

struct edge{
    int to,cost;
};

void solve(){
    int n,x;
    cin >> n >> x;
    vector<vector<edge>> graph(n);
    rep(i,0,n-1){
        int x,y,c;
        cin >> x >> y >> c;
        --x;
        --y;
        graph[x].push_back(edge({y,c}));
        graph[y].push_back(edge({x,c}));
    }

    vector<int> subtree_size(n);
    vector<bool> centroid(n);
    function<i64(int)> rec=[&](int u){
        compute_subtree_size<vector<vector<edge>>>(graph,centroid,subtree_size,u,-1);
        int s=search_centroid(graph,centroid,subtree_size,u,-1,subtree_size[u]).second;
        centroid[s]=true;
    
        function<void(map<int,i64>&,int,int,int)> dfs=[&](map<int,i64> &m,int v,int p,int s){
            ++m[s];
            for(edge &e:graph[v]){
                if(e.to==p or centroid[e.to]) continue;
                dfs(m,e.to,v,s^e.cost);
            }
        };

        i64 res=0;
        {
            map<int,i64> m;
            dfs(m,s,-1,0);
            for(auto &p:m){
                if(p.first==(p.first^x)) res+=p.second*(p.second-1);
                else res+=p.second*m[p.first^x];
                m[p.first^x]=0;
            }
        }
        for(edge &e:graph[s]){
            if(centroid[e.to]) continue;
            res+=rec(e.to);
            map<int,i64> m;
            dfs(m,e.to,s,e.cost);
            for(auto &p:m){
                if(p.first==(p.first^x)) res-=p.second*(p.second-1);
                else res-=p.second*m[p.first^x];
                m[p.first^x]=0;
            }
        }
        centroid[s]=false;
        return res;
    };
    cout << rec(0) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User walkre
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3532 Byte
Status WA
Exec Time 1223 ms
Memory 21248 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 25
WA × 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 WA 2 ms 384 KB
subtask1_03.txt AC 1177 ms 19200 KB
subtask1_04.txt AC 1183 ms 21248 KB
subtask1_05.txt AC 1223 ms 19200 KB
subtask1_06.txt WA 135 ms 20224 KB
subtask1_07.txt AC 341 ms 6656 KB
subtask1_08.txt AC 313 ms 6656 KB
subtask1_09.txt AC 940 ms 7680 KB
subtask1_10.txt AC 918 ms 7680 KB
subtask1_11.txt AC 3 ms 384 KB
subtask1_12.txt AC 3 ms 384 KB
subtask1_13.txt AC 650 ms 6784 KB
subtask1_14.txt AC 653 ms 6784 KB
subtask1_15.txt AC 72 ms 1664 KB
subtask1_16.txt AC 72 ms 1664 KB
subtask1_17.txt AC 71 ms 1664 KB
subtask1_18.txt AC 72 ms 1664 KB
subtask1_19.txt AC 73 ms 1664 KB
subtask1_20.txt AC 72 ms 1664 KB
subtask1_21.txt AC 72 ms 1664 KB
subtask1_22.txt AC 73 ms 1664 KB
subtask1_23.txt AC 71 ms 1664 KB
subtask1_24.txt AC 75 ms 1664 KB