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> ¢roid,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> ¢roid,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 |
|
|
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 |