-
Notifications
You must be signed in to change notification settings - Fork 0
/
GERALD08.cpp
106 lines (100 loc) · 2.09 KB
/
GERALD08.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cassert>
#include<cmath>
/*
Did not get AC on Contest.
*/
using namespace std;
struct node{
int index, edge;
node( int a, int b){
index = a;
edge = b;
}
};
struct treenode{
vector<struct node> children;
};
treenode tree[100005];
const double eps = 1e-8;
double compute( int root){
double nodeGameValue = 0.0;
for(int i = 0; i < tree[root].children.size(); i++){
int childIndex = tree[root].children[i].index;
int color = tree[root].children[i].edge;
assert( color == 1 || color == 0);
double gameValue = compute(childIndex);
if(color == 0){//black or blue
double k=0;
if(gameValue > 0){// x+1 should suffice
k = 1.0;
}
else{
k = ceil(1.0 - gameValue);
if( fabs ( gameValue - (long long)gameValue) < eps)// gameValue is an integer
k = k + 1.0;
gameValue = gameValue + k;
assert(gameValue > 1.0);
gameValue = gameValue / pow(2.0, k-1);
}
}
else{//white or red
double k =0;
if(gameValue < 0){//x-1 should suffice
k = 1.0;
}
else{
double k = ceil(gameValue + 1);
if( fabs (gameValue - (long long)gameValue) < eps )//gameValue is an integer
k = k + 1.0;
gameValue = gameValue - k;
assert(gameValue < -1.0);
gameValue = gameValue / pow(2.0, k-1);
}
}
nodeGameValue += gameValue;
}
//printf("gameValue for tree rooted at %d is %lf\n", root, nodeGameValue);
return nodeGameValue;
}
int main(){
int t,n,u,v,c;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for( int i = 1; i <=n; i++)
tree[i].children.clear();
for(int i = 1; i < n; i++){
scanf("%d%d%d",&u,&v,&c);
if(u > v)
swap(u,v);
tree[u].children.push_back( node(v,c));
}
/*
//printing the tree
queue<int> q;
q.push(1);
while(!q.empty()){
int a = q.front();
q.pop();
printf("%d ",a);
for( int i =0; i<tree[a].children.size(); i++){
q.push(tree[a].children[i].index);
}
}
puts("");
*/
double d = compute(1);
//printf("%lf ",d);
if(d > 0)
puts("Chef Chef");
else if(d < 0)
puts("Ksen Ksen");
else
puts("Ksen Chef");
}
}