Light OJ - 1355 - Game of CS Tutorial

প্রব্লেমটি Green Hackenbush এর সুন্দর একটি প্রব্লেম। প্রব্লেম পড়ে থাকলে এবং Green Hackenbush বুঝে থাকলে, এটুকু নিশ্চয়ই বুঝেছো যে ১ একক দৈর্ঘ্যের এজ গুলো নিয়ে কোন সমস্যা নেই। বিপত্তি শুরু হয় যখন এজ এর দৈর্ঘ্য ১ এর বেশি হয়। 

কয়েকটি কেস এনালাইসিস করলে বুঝবে যে যেসব এজ এর দৈর্ঘ্য এক এর বেশি তারা একটি লুপ এর মতো কাজ করে। অর্থাৎ, x>1 দৈর্ঘ্যের একটি এজকে আমি x সংখ্যক একক দৈর্ঘ্যের এজ দ্বারা রিপ্লেস করতে পারি। 

এখন, একটি এজ [u,v] এর জন্য হিসেবটা কেমন হবে? 

১) যদি এজটির কস্ট = ১ হয়, তাহলে value[u] ^= (1 + value[v])

২) অন্যথায়, 

        i) কস্ট যদি বিজোড় হয়, তাহলে value[u] ^= (1 ^ value[v])       (Think about it by pen & papper)

        ii) কস্ট যদি জোড় হয়, তাহলে value[u] ^= value[v]

আশা করি এখন প্রব্লেমটি তোমার কাছে একটি স্ট্রেইট ফরোয়ার্ড প্রবেলেমে রূপান্তরিত হয়েছে। তাও না পারলে সলুশন দেখতে পারো। 

	#include<bits/stdc++.h>
	#define sc scanf
	#define scin(x) sc("%d",&(x))
	#define scin2(x,y) sc("%d %d",&(x),&(y))
	#define pf printf
	#define vi vector<int>
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	#define sz 1005
	vi graph[sz],cost[sz];
	int vis[sz],value[sz];
	void DFS(int u)
	{
	vis[u] = 1;
	int XOR = 0;
	for(int i=0 ; i<(int)graph[u].size() ; i++){
	int v = graph[u][i];
	int wt = cost[u][i];
	if(!vis[v]){
	DFS(v);
	if(wt == 1) /** There is a simple path from u to v **/
	value[v] = 1 + value[v];
	else if(wt%2 == 1) /** There is a loop from u to v & length of loop = wt. So, according to fusion principle replace the wt length loop with wt edges of 1 unit. And all these edges will connected to node u. And node v is now also in node u **/
	value[v] = (1 ^ value[v]);
	else
	value[v] = value[v];
	XOR ^= value[v];
	}
	}
	value[u] = XOR;
	}
	void Clean(int n)
	{
	for(int i=0 ; i<=n+2 ; i++){
	graph[i].clear();
	cost[i].clear();
	vis[i] = value[i] = 0;
	}
	}
	void Solve(int t)
	{
	int i,j,k,n,u,v,w;
	scin(n);
	for(i=1 ; i<n ; i++){
	sc("%d %d %d",&u,&v,&w);
	graph[u].pb(v);
	graph[v].pb(u);
	cost[u].pb(w);
	cost[v].pb(w);
	}
	DFS(0);
	if(value[0])
	pf("Case %d: Emily\n",t);
	else
	pf("Case %d: Jolly\n",t);
	Clean(n);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1355.cpp hosted with ❤ by GitHub