1
29
2018
0

TC-SRM-545-div1-975

考虑每位独立,容斥即可。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
LL ans,p2[55];
int n,m,tmp[55],fa[55],a[55][55];
bool b[55];
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
void dfs(int x,int s,int blk){
	if (x>m){
		if (s&1) ans-=p2[blk]-2; else ans+=p2[blk]-2;
		return;
	}
	int FA[n+1];
	FOR(i,1,n) FA[i]=fa[i];
	b[x]=0;
	dfs(x+1,s,blk);
	FOR(i,1,n) fa[i]=FA[i];
	b[x]=1;
	FOR(j,2,a[x][0]){
		int y=a[x][j];
		int X=getf(a[x][1]),Y=getf(y);
		if (X!=Y) fa[X]=Y,--blk;
	}
	dfs(x+1,s+1,blk);
}
class SetAndSet{
	public:
	long long countandset(vector<int> A){
		n=A.size();
		p2[0]=1;
		FOR(i,1,n) p2[i]=p2[i-1]*2;
		m=0;
		FOR(i,0,19){
			FOR(j,1,n) tmp[j]=(A[j-1]>>i)&1;
			bool ok=1;
			FOR(j,2,n) if (tmp[j]!=tmp[1]) ok=0;
			if (ok) continue;
			++m;
			FOR(j,1,n) if (!tmp[j]) a[m][++a[m][0]]=j;
		}
		FOR(i,1,n) fa[i]=i;
		dfs(1,0,n);
		return ans;
	}
}cwy;
Category: TC | Tags:
1
28
2018
0

TC-SRM-590-div1-1000

原图相当于一些限制,要最小化代价,最小割模型。

Category: TC | Tags:
1
28
2018
0

TC-SRM-647-div1-950

删掉垃圾点后,对于(u,v,cost)连上(u,v,cost)和(v,u,INF),即可保证存在到达关系的两条边不会同时被割。

Category: TC | Tags:
1
27
2018
0

TC-SRM-491-div1-900

二分答案后跑费用流。

Category: TC | Tags:
1
26
2018
0

TC-SRM-494-div1-1000

知道了两行一列之后剩下的直接表示出来,然后列方程,高斯消元。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
const int MO=123456789;
const int dx[]={0,-1,-2,-1,-2,1,1,2,2};
const int dy[]={0,-2,-1,2,1,-2,2,-1,1};
bitset<455> o[155][155];
bitset<455> a[455];
int n,m,N,M;
class KnightsOut{
	public:
	int guass(){
		int now=0;
		FOR(i,1,m){
			int t=0;
			FOR(j,now+1,n)
				if (a[j][i]) t=j;
			if (!t) continue;
			++now;
			swap(a[t],a[now]);
			FOR(j,now+1,n)
				if (a[j][i]) a[j]^=a[now];
		}
		/*
		puts("");
		FOR(i,1,n){
			FOR(j,1,m+1) cout<<a[i][j];
			puts("");
		}
		*/
		FOR(i,now+1,n)
			if (a[i][m+1]) return 0;
		int ans=1;
		FOR(i,1,m-now) ans=ans*2%MO;
		return ans;
	}
	int count(int NN, int MM){
		N=NN,M=MM;
		if (N<2) return 1;
		m=0;
		FOR(i,1,N)
			FOR(j,1,M)
				if (i<=2 || j<=1){
					++m;
					o[i][j][m]=1;
				}
		FOR(i,1,N-2)
			FOR(j,1,M-1){
				FOR(d,0,7){
					if (i+dx[d]<1 || i+dx[d]>N || j+dy[d]<1 || j+dy[d]>M) continue;
					o[i+2][j+1]^=o[i+dx[d]][j+dy[d]];
				}
				o[i+2][j+1][m+1]=o[i+2][j+1][m+1]^1;
			}
		/*
		FOR(i,1,N)
			FOR(j,1,M){
				FOR(k,1,m+1) cout<<o[i][j][k];
				puts("");
			}
		*/
		FOR(i,1,N)
			FOR(j,1,M)
				if (i>N-2 || j>M-1){
					++n;
					FOR(d,0,8){
						int x=i+dx[d],y=j+dy[d];
						if (x<1 || x>N || y<1 || y>M) continue;
						a[n]^=o[x][y];
					}
					a[n][m+1]=a[n][m+1]^1;
				}
		/*
		puts("");
		FOR(i,1,n){
			FOR(j,1,m+1) cout<<a[i][j];
			puts("");
		}
		*/
		return guass();
	}
}cwy;
Category: TC | Tags:
1
25
2018
0

TC-SRM-620-div1-800

高斯消元求自由元

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
const int MO=1e9+7;
int a[1111][1111],n,p[1111][1111],m,tot,N,now;
map<int,int> M;
vector<int> v[100010];
class PerfectSquare{
	public:
	int guass(){
		now=0;
		FOR(i,1,N){
			int w=0;
			for (int j=now+1;j<=m;j++)
				if (a[j][i]==1){
					w=j;
					break;
				}
			if (!w) continue;
			++now;
			FOR(j,1,N+1) swap(a[w][j],a[now][j]);
			FOR(j,now+1,m)
				if (a[j][i]){
					FOR(k,1,N+1) a[j][k]^=a[now][k];
				}
		}
		FOR(i,now+1,m)
			if (a[i][N+1]!=0) return 0;
		int t=N-now;
		LL ans=1;
		while (t--) ans=(ans<<1)%MO;
		return (int)ans;
	}
	int ways(vector <int> x){
		n=sqrt(x.size());
		N=n*n;
		int t=0;
		tot=0;
		FOR(i,1,n)
			FOR(j,1,n){
				int A=x[t];
				p[i][j]=++t;
				for (int k=2;k*k<=A;++k){
					int cnt=0;
					while (A%k==0) cnt^=1,A/=k;
					if (cnt){
						if (M.find(k)==M.end()) M[k]=++tot;
						v[M[k]].pb(t);
					}
				}
				if (A>1){
					if (M.find(A)==M.end()) M[A]=++tot;
					v[M[A]].pb(t);
				}
			}
		m=0;
		FOR(i,1,n){
			++m;
			FOR(j,1,n)
				a[m][p[i][j]]=1;
			a[m][N+1]=1;
		}
		FOR(j,1,n){
			++m;
			FOR(i,1,n)
				a[m][p[i][j]]=1;
			a[m][N+1]=1;
		}
		FOR(i,1,tot){
			++m;
			for (int j=0;j<v[i].size();++j){
				int x=v[i][j];
				a[m][x]=1;
			}
		}
		return guass();
	}
}cwy;
Category: TC | Tags:
1
25
2018
0

TC-SRM-580-div1-1000

f[i][j]表示走到(i,j)的....

转移分3种

1.拦的人硬点

2.走的人拐弯一次

3.走的人拐弯两次

奥妙重重得过了。

考虑正确性更显然的做法,容易知道一行里面拦的墙是连续的一段,状态改成3维后容易转移。

Category: TC | Tags:
12
4
2017
0

TC-SRM-570-div1-900

首先如果判断是否有解很容易想到直接网格图黑白染色后求最大流来判。

问题在于这题是有费用的,而且费用的条件很奇怪。

考虑如何区分弯轨道和直轨道,不难发现,弯轨道总是匹配了一个同行的点,和一个同列的点。与此相反,直轨道总是匹配了两个同行/同列的点。

于是拆点,把点拆成2个表示行和列,两个连之间连流量1费用0|1的双向边,求最小费用最大流即可。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;

const int INF=1e9+10;
const int qs=1e7;
const int dx[]={-1,0,0,1};
const int dy[]={0,-1,1,0};
bool u[100010];
char a[111][111];
int d[100010],p[111][111][2],n,m,S,T,nedge,hed[100010],cst[100010],c[111][111],las[100010],lnk[100010],too[100010],nxt[100010],cap[100010],q[qs];
class CurvyonRails{
	public:
	void ae(int x,int y,int f,int c){
		nxt[++nedge]=hed[x];
		hed[x]=nedge;
		too[nedge]=y;
		cap[nedge]=f;
		cst[nedge]=c;
	}
	void add(int x,int y,int f,int c){
		ae(x,y,f,c),ae(y,x,0,-c);
	}
	bool spfa(){
		int he=0,ta=1;
		q[1]=S;
		u[S]=1;
		FOR(i,S,T) d[i]=INF;
		d[S]=0;
		while (he!=ta){
			int x=q[(++he)%=qs];
			u[x]=0;
			for (int i=hed[x];i;i=nxt[i]){
				int y=too[i];
				if (!cap[i] || d[x]+cst[i]>=d[y]) continue;
				d[y]=d[x]+cst[i];
				las[y]=x,lnk[y]=i;
				if (!u[y]) u[y]=1,q[(++ta)%=qs]=y;
			}
		}
		return (d[T]<INF);
	}
	int mcmf(){
		int ans=0,flo=0;
		while (spfa()){
			int t=INF;
			for (int i=T;i!=S;i=las[i]) t=min(t,cap[lnk[i]]);
			flo+=t;
			for (int i=T;i!=S;i=las[i])	cap[lnk[i]]-=t,cap[lnk[i]^1]+=t;
			ans+=t*d[T];
		}
		if (flo==T/2) return ans;
		else return (-1);
	}
	int getmin(vector<string> field){
		n=field.size();
		m=field[0].size();
		FOR(i,1,n)
			FOR(j,1,m)
				a[i][j]=field[i-1][j-1];
		nedge=1;
		S=0;
		T=0;
		FOR(i,1,n)
			FOR(j,1,m)
				c[i][j]=(i&1)^(j&1);
		FOR(i,1,n)
			FOR(j,1,m)
				if (a[i][j]!='w') p[i][j][0]=++T,p[i][j][1]=++T;
		++T;
		FOR(i,S,T) hed[i]=0;
		FOR(i,1,n)
			FOR(j,1,m){
				if (a[i][j]=='w') continue;
				if (!c[i][j]) add(S,p[i][j][0],1,0),add(S,p[i][j][1],1,0);
				else add(p[i][j][0],T,1,0),add(p[i][j][1],T,1,0);
				add(p[i][j][0],p[i][j][1],1,(a[i][j]=='C'));
				add(p[i][j][1],p[i][j][0],1,(a[i][j]=='C'));
			}
		FOR(x,1,n)
			FOR(y,1,m){
				if (a[x][y]=='w') continue;
				if ((x&1)^(y&1)) continue;
				FOR(d,0,3){
					int X=x+dx[d],Y=y+dy[d];
					if (X<1 || X>n || Y<1 || Y>m) continue;
					if (a[X][Y]=='w') continue;
					if (d==1 || d==2) add(p[x][y][0],p[X][Y][0],1,0);
					else add(p[x][y][1],p[X][Y][1],1,0);
				}
			}
		return (mcmf());
	}
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {".."
,".."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(0, Arg1, getmin(Arg0)); }
	void test_case_1() { string Arr0[] = {"wCCww"
,"wCC.."
,"..w.."
,"....w"
,"ww..w"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(1, Arg1, getmin(Arg0)); }
	void test_case_2() { string Arr0[] = {"C.w"
,"..."
,".C."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(2, Arg1, getmin(Arg0)); }
	void test_case_3() { string Arr0[] = {"."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(3, Arg1, getmin(Arg0)); }
	void test_case_4() { string Arr0[] = {"w"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(4, Arg1, getmin(Arg0)); }
	void test_case_5() { string Arr0[] = {"CC..CCCw.CwC..CC.w.C",
 "C.CCCwCCC.w.w..C.w..",
 "wwww...CC.wC.Cw.CC..",
 "CC..CC.w..w.C..CCCC.",
 "CC.CCC..CwwCCC.wCC..",
 "w.C..wwCC.CC.wwwCC..",
 ".CC.CC..CCC..CC.CC.C",
 "Cw....C.C.CCC...CC..",
 "CC.C..Cww.C.CwwwC..w",
 "wCCww..C...CCCCCCC.w",
 "C.CCw.CC.ww...C.CCww",
 "C.C.C.CCwCC..wCCw.Cw",
 "CCC.C...w..C.wC.wCCw",
 "CC.C..C..CCC.CC.C...",
 "C.ww...CCC..CC...CCC",
 "...CCC.CwwwC..www.C.",
 "wwCCCCC.w.C.C...wCwC",
 "CCwC.CwCCC.C.w.Cw...",
 "C.w.wC.CC.CCC.C.w.Cw",
 "CCw.CCC..C..CC.CwCCw",
 "C.wwwww.CwwCCwwwwwww"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 9; verify_case(5, Arg1, getmin(Arg0)); }

// END CUT HERE
}cwy;
Category: TC | Tags:
12
1
2017
0

TC-SRM-569-div1-1000

首先考虑10进制怎么做,我们只要统计质因子5的个数。

然后我想到了直接写成带组合数的求和式子,发现根本不会算。

其实,我们改写式子可以转化为加法。

这样k<=16就可以考虑矩阵乘法了。

然后发现这个矩阵乘法不太好处理,因为每个数的质因子里5的数量不同,所以无法写出常数项的系数。

考虑倍增(不是平常的2倍而是5倍),可以不是直接矩阵乘法乘到底,而是根据5进制来乘。

求出n=0到n=5^i的转移矩阵后,容易求出n=0到n=5^(i+1)的转移矩阵。

之后把n拆成5进制从高位到低位乘就好了。

细节:比如对于b=8,我们要求的是他因子有k个2,[k/3]%(1e9+9)才是答案,所以我们中途要%的是(1e9+9)*3,刚好不会炸long long。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;

LL MO;
int n,k,b,C,top,stk[555];
struct mat{
	LL p[20][20];
	mat(){memset(p,0,sizeof(p));}
	mat operator * (const mat & A) const{
		mat B;
		FOR(a,0,k)
			FOR(b,0,k)
				FOR(c,0,k)
					(B.p[a][b]+=p[a][c]*A.p[c][b]%MO)%=MO;
		return B;
	}
	void clear(){
		memset(p,0,sizeof(p));
	}
}Q[50],A,B;
class MegaFactorial{
	public:
	mat cal(int n){
		FOR(w,1,49){
			Q[w]=Q[w-1];
			FOR(i,2,C) Q[w]=Q[w]*Q[w-1];
			FOR(i,1,k) (++Q[w].p[0][i])%=MO;
		}
		top=-1;
		while (n){
			stk[++top]=n%C;
			n/=C;
		}
		mat t;
		FOR(i,0,k) t.p[i][i]=1;
		FORD(i,top,0)
			FOR(j,1,stk[i])
				t=t*Q[i];
		return t;
	}
	int countTrailingZeros(int N, int K, int BB){
		A.clear();
		B.clear();
		Q[0].clear();
		n=N;
		k=K;
		b=BB;
		A.p[0][0]=1;
		FOR(i,0,k)
			FOR(j,0,k)
				if (i==0) Q[0].p[i][j]=(j==0);
				else Q[0].p[i][j]=(j>=i);
		if (b==2 || b==3 || b==5 || b==7){
			MO=1e9+9;
			C=b;
			B=cal(n);
			A=A*B;
			return (int)A.p[0][k];
		}
		else if (b==6 || b==10){
			C=b>>1;
			MO=1e9+9;
			B=cal(n);
			A=A*B;
			return (int)A.p[0][k];
		}
		else if (b==4){
			C=2;
			MO=1e9+9,MO=MO*2;
			B=cal(n);
			A=A*B;
			return int((A.p[0][k]/2)%1000000009);
		}
		else if (b==8){
			C=2;
			MO=1e9+9,MO=MO*3;
			B=cal(n);
			A=A*B;
			return int((A.p[0][k]/3)%1000000009);
		}
		else if (b==9){
			C=3;
			MO=1e9+9,MO=MO*2;
			B=cal(n);
			A=A*B;
			return int((A.p[0][k]/2)%1000000009);
		}
	}
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { int Arg0 = 6; int Arg1 = 1; int Arg2 = 4; int Arg3 = 2; verify_case(0, Arg3, countTrailingZeros(Arg0, Arg1, Arg2)); }
	void test_case_1() { int Arg0 = 4; int Arg1 = 2; int Arg2 = 6; int Arg3 = 2; verify_case(1, Arg3, countTrailingZeros(Arg0, Arg1, Arg2)); }
	void test_case_2() { int Arg0 = 10; int Arg1 = 3; int Arg2 = 10; int Arg3 = 22; verify_case(2, Arg3, countTrailingZeros(Arg0, Arg1, Arg2)); }
	void test_case_3() { int Arg0 = 50; int Arg1 = 10; int Arg2 = 8; int Arg3 = 806813906; verify_case(3, Arg3, countTrailingZeros(Arg0, Arg1, Arg2)); }
	void test_case_4() { int Arg0 = 1000000000; int Arg1 = 16; int Arg2 = 2; int Arg3 = 633700413; verify_case(4, Arg3, countTrailingZeros(Arg0, Arg1, Arg2)); }
// END CUT HERE
}cwy;
Category: TC | Tags:
11
27
2017
0

TC-SRM-568-div1-1000

https://284914869.github.io/AEoj/568.html

TC竟然还有数据范围是50的非多项式题。。。

当已经有连边的比较多的时候,直接暴力枚举剩下的连边,判一下。

当已经有连边的比较少的时候,直接暴力枚举已经连边的方向,剩下的合法当且仅当

对于每个已经确定的半圆,它里面跟他同向的点数量是偶数,知道这个后带权并查集判一下。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;

bool ok;
int n,m,a[1111],U[1111],stk[1111],ts,top,b[1111],fa[1111],d[1111];
pa tmp[1111];
class DisjointSemicircles{
	public:
	bool crs(int x,int y){
		return (tmp[x].fi>=tmp[y].fi && tmp[x].fi<=tmp[y].se)^(tmp[x].se>=tmp[y].fi && tmp[x].se<=tmp[y].se);
	}
	int getf(int x){
		if (fa[x]==x) return x;
		int t=fa[x];
		fa[x]=getf(fa[x]);
		d[x]^=d[t];
		return fa[x];
	}
	void ck(){
		FOR(i,0,top) fa[i]=i,d[i]=0;
		FOR(i,1,ts){
			int x=lower_bound(stk+1,stk+top+1,tmp[i].fi)-stk,y=upper_bound(stk+1,stk+top+1,tmp[i].se)-stk-1;
			if (x>y) continue;
			//y-x+1
			int X=getf(x-1),Y=getf(y),t;
			if (U[i]==0) t=(y-x+1)&1;
			else t=0;
			if (X==Y){
				if (d[x-1]^d[y]^t) return;
			}
			else{
				fa[X]=Y;
				d[X]=d[x-1]^d[y]^t;
			}
		}
		int X=getf(0),Y=getf(top);
		if (X==Y && d[0]^d[top]) return;
		FOR(i,0,top) fa[i]=getf(fa[i]);
		ok=1;
	}
	void dfs(int x){
		if (ok) return;
		if (x>ts){
			ck();
			return;
		}
		bool flag=1;
		FOR(i,1,x-1)
			if (U[i]==0 && crs(i,x)){flag=0;break;}
		if (flag){
			U[x]=0;
			dfs(x+1);
		}
		flag=1;
		FOR(i,1,x-1)
			if (U[i]==1 && crs(i,x)){flag=0;break;}
		if (flag){
			U[x]=1;
			dfs(x+1);
		}
	}
	string getPossibility(vector<int> labels){
		ok=0;
		n=labels.size();
		FOR(i,1,n) a[i]=labels[i-1];
		FOR(i,1,n)
			FOR(j,1,n)
				if (a[i]!=-1 && i!=j && a[i]==a[j]) b[i]=j;
		ts=0;
		FOR(i,1,n)
			if (b[i]>i && a[i]!=-1) tmp[++ts]=mp(i,b[i]);
		top=0;
		FOR(i,1,n) if (a[i]==-1) stk[++top]=i;
		dfs(1);
		return (ok?"POSSIBLE":"IMPOSSIBLE");
	}
	// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { int Arr0[] = { -1, 0, -1, -1, 0, -1 }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "POSSIBLE"; verify_case(0, Arg1, getPossibility(Arg0)); }
	void test_case_1() { int Arr0[] = { 1, -1, 2, 1, -1, 2 }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "IMPOSSIBLE"; verify_case(1, Arg1, getPossibility(Arg0)); }
	void test_case_2() { int Arr0[] = { 2, -1, -1, 0, -1, -1, 2, 0 }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "POSSIBLE"; verify_case(2, Arg1, getPossibility(Arg0)); }
	void test_case_3() { int Arr0[] = { -1, 1, 3, -1, 1, 3, -1, -1 }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "IMPOSSIBLE"; verify_case(3, Arg1, getPossibility(Arg0)); }
	void test_case_4() { int Arr0[] = { -1, 5, -1, -1, 3, 6, 8, -1, 10, 7, -1, 7, 8, 0, 11, -1, -1, 11, 0, 10, 4, -1, 6, 5, -1, -1, 9, 9, 4, 3 }
; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "POSSIBLE"; verify_case(4, Arg1, getPossibility(Arg0)); }
	void test_case_5() { int Arr0[] = { 4, -1, 2, 4, -1, 3, 3, 12, 2, 5, -1, 0, 9, 9, 8, -1, 12, 8, -1, 6, 0, -1, -1, -1, 5, 6, 10, -1, -1, 10 }
; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "IMPOSSIBLE"; verify_case(5, Arg1, getPossibility(Arg0)); }
	void test_case_6() { int Arr0[] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "POSSIBLE"; verify_case(6, Arg1, getPossibility(Arg0)); }

// END CUT HERE
}cwy;
Category: TC | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com