Submission #3585632
Source Code Expand
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
prayer
*/
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(__,v.size()){rep(_,v[__].size())cout<<" "<<v[__][_];cout<<endl;}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
signed main(){
int n;
cin>>n;
vvp G(n);
rep(i,n-1){
int a,b,c;
cin>>a>>b>>c;
G[a].pb({b,c});
G[b].pb({a,c});
}
map<int,int>ma;
rep(i,n){
int x=0;
rep(j,G[i].size())x^=G[i][j].second;
if(x)ma[x]++;
}
int m=0,out=0;
FOR(a,ma){
out+=a.second/2;
if(a.second%2)m+=1<<a.first;
}
m/=2;
vi dp(1<<15,-inf);
dp[0]=0;
rep(i,1<<15){
rep(j,15)if((i&1<<j)==0)cmax(dp[i|1<<j],dp[i]);
int t=1<<15;
t-=1+i;
for(int j=t;j>0;j=(j-1)&t){
int x=0,c=0;
rep(k,15)if(j&1<<k)x^=1+k,c++;
if(x)continue;
cmax(dp[i|j],dp[i]+c-1);
}
}
cout<<out+dp[m]<<endl;
}
Submission Info
Submission Time |
|
Task |
F - XOR Tree |
User |
ixmel_rd |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3045 Byte |
Status |
WA |
Exec Time |
773 ms |
Memory |
10112 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt |
All |
0_000.txt, 0_001.txt, 1_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
664 ms |
512 KB |
0_001.txt |
AC |
664 ms |
512 KB |
1_002.txt |
AC |
764 ms |
8064 KB |
1_003.txt |
AC |
768 ms |
8064 KB |
1_004.txt |
WA |
766 ms |
8064 KB |
1_005.txt |
AC |
766 ms |
10112 KB |
1_006.txt |
WA |
769 ms |
8064 KB |
1_007.txt |
AC |
769 ms |
8064 KB |
1_008.txt |
AC |
769 ms |
8064 KB |
1_009.txt |
AC |
767 ms |
8064 KB |
1_010.txt |
WA |
765 ms |
8064 KB |
1_011.txt |
WA |
773 ms |
8064 KB |
1_012.txt |
WA |
754 ms |
7536 KB |
1_013.txt |
AC |
751 ms |
9584 KB |
1_014.txt |
WA |
753 ms |
7536 KB |
1_015.txt |
WA |
759 ms |
7536 KB |
1_016.txt |
WA |
754 ms |
7536 KB |
1_017.txt |
WA |
754 ms |
7536 KB |
1_018.txt |
WA |
755 ms |
7536 KB |
1_019.txt |
WA |
762 ms |
7536 KB |
1_020.txt |
AC |
753 ms |
7536 KB |
1_021.txt |
WA |
764 ms |
7536 KB |
1_022.txt |
AC |
755 ms |
7536 KB |
1_023.txt |
WA |
753 ms |
7536 KB |
1_024.txt |
WA |
754 ms |
8048 KB |
1_025.txt |
WA |
754 ms |
7536 KB |
1_026.txt |
WA |
748 ms |
7536 KB |
1_027.txt |
WA |
749 ms |
7536 KB |
1_028.txt |
WA |
753 ms |
7536 KB |
1_029.txt |
WA |
753 ms |
7536 KB |
1_030.txt |
WA |
752 ms |
8944 KB |
1_031.txt |
WA |
753 ms |
7536 KB |
1_032.txt |
WA |
755 ms |
7536 KB |
1_033.txt |
AC |
763 ms |
8064 KB |
1_034.txt |
WA |
762 ms |
8064 KB |
1_035.txt |
AC |
765 ms |
8064 KB |
1_036.txt |
WA |
760 ms |
8064 KB |
1_037.txt |
WA |
764 ms |
8064 KB |
1_038.txt |
WA |
765 ms |
8064 KB |
1_039.txt |
WA |
766 ms |
8064 KB |
1_040.txt |
AC |
764 ms |
8064 KB |
1_041.txt |
AC |
765 ms |
8064 KB |
1_042.txt |
WA |
765 ms |
8064 KB |