2017-2018 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

A. Odd Palindrome

所有回文子串长度都是奇数等价于不存在长度为$2$的偶回文子串，即相邻两个字符都不同。

#include<cstdio>

#include<cstring>

char a[1111111];int n,i;

int main(){

	scanf("%s",a+1);

	n=strlen(a+1);

	for(i=1;i<n;i++)if(a[i]==a[i+1])return puts("Or not."),0;

	puts("Odd.");

}

B. Enlarging Enthusiasm

注意到方案数不超过$(n-1)\times (n-1)!$，爆搜出所有可行方案即可，需要大量常数优化。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=15;

int n,m,i,a[N],f[(1<<12)+5],ans;

int cnt[(1<<12)+5];

int w[N];

void dfs(int S,int mx,int q,int x){

	if(!S){

		ans++;

		return;

	}

	mx++;

	if((S&-S)==S){

		int j=f[S];

		int nowq=mx-j>q?mx-j:q;

		if(x>=nowq)ans++;

		return;

	}

	int U=S;

	while(U){

		int i=U&-U,j=f[i];

		int nowq=mx-j>q?mx-j:q;

		if(x>=nowq)dfs(S^i,j+nowq,nowq,x-nowq);

		U^=i;

	}

}

void gao(int S,int mx,int q,int x){

	if(!S){

		ans++;

		return;

	}

	mx++;

	for(int U=S;U;U-=U&-U){

		int i=U&-U;

		if(i==(1<<(n-1)))continue;

		int nowq=mx-f[i];

		if(nowq<q)nowq=q;

		if(x>=nowq)dfs(S^i,f[i]+nowq,nowq,x-nowq);

	}

}

int main(){

	scanf("%d%d",&n,&m);

	for(i=1;i<1<<n;i++)cnt[i]=cnt[i>>1]+(i&1);

	for(w[0]=i=1;i<=n;i++)w[i]=w[i-1]*i;

	for(i=0;i<n;i++)scanf("%d",&a[i]);

	sort(a,a+n);

	for(i=0;i<n;i++)f[1<<i]=a[i];

	gao((1<<n)-1,a[n-1],0,m);

	printf("%d",ans);

}

/*

12 700

1 2 3 4 5 6 7 8 9 10 11 12

*/

C. Fear Factoring

考虑每个约数的贡献，那么分段等差数列求和即可。

时间复杂度$O(\sqrt{b})$。

#include<cstdio>

typedef long long ll;

ll cal(ll n){

	ll i,j;

	ll ans=0;

	for(i=1;i<=n;i=j+1){

		j=n/(n/i);

		ans+=(i+j)*(j-i+1)*(n/i);

	}

	return ans;

}

int main(){

	ll a,b;

	scanf("%lld%lld",&a,&b);

	printf("%lld",(cal(b)-cal(a-1))/2);

}

D. Rainbow Roads

对于每个点，若其有超过一条同色的边，那么对应子树都不是Good点，差分前缀和打标记即可。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef pair<int,int>P;

const int N=300010;

int n,i,j,k,x,y,z,g[N],v[N],w[N],nxt[N],ed;

int f[N],dfn,st[N],en[N];

int m,ans,s[N];

P q[N];

inline void add(int x,int y,int z){

	v[++ed]=y;

	w[ed]=z;

	nxt[ed]=g[x];

	g[x]=ed;

}

void dfs(int x,int y){

	st[x]=++dfn;

	f[x]=y;

	for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x);

	en[x]=dfn;

}

int main(){

	scanf("%d",&n);

	for(i=1;i<n;i++){

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z),add(y,x,z);

	}

	dfs(1,0);

	for(i=1;i<=n;i++){

		m=0;

		for(j=g[i];j;j=nxt[j])q[++m]=P(w[j],v[j]);

		sort(q+1,q+m+1);

		for(j=1;j<=m;j=k){

			for(k=j;k<=m&&q[j].first==q[k].first;k++);

			if(k>j+1){

				for(x=j;x<k;x++){

					y=q[x].second;

					if(y==f[i]){

						s[1]++;

						s[st[i]]--;

						s[en[i]+1]++;

					}else{

						s[st[y]]++;

						s[en[y]+1]--;

					}

				}

			}

		}

	}

	for(i=1;i<=n;i++)s[i]+=s[i-1];

	for(i=1;i<=n;i++)if(!s[st[i]])ans++;

	printf("%d\n",ans);

	for(i=1;i<=n;i++)if(!s[st[i]])printf("%d\n",i);

}

E. Straight Shot

二分水平分速度，检查最终是否走到了$(x,0)$。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=111;

int n,i;

double X,V,dx,dy;

double lim,goal=1e100,tmp,L,R,MID,l[N],r[N],v[N];

double cal(double dy){

	double dx=sqrt(V*V-dy*dy);

	double x=0,y=0;

	for(int i=1;i<=n;i++){

		y+=dy*(l[i]-x);

		y+=(dy+v[i])*(r[i]-l[i]);

		x=r[i];

	}

	y+=dy*(X-x);

	tmp=X/dx;

	return y/dx;

}

int main(){

	scanf("%d%lf%lf",&n,&X,&V);

	for(i=1;i<=n;i++)scanf("%lf%lf%lf",&l[i],&r[i],&v[i]);

	L=-V,R=V;

	for(int _=1000;_;_--){

		MID=(L+R)/2;

		if(cal(MID)<0)L=MID;else R=MID;

	}

	lim=X/V*2;

	L=(L+R)/2;

	if(fabs(cal(L))<1e-8){

		cal(L);

		goal=tmp;

	}

	if(goal>lim+1e-8)puts("Too hard");

	else printf("%.3f",goal);

}

F. Distinct Distances

答案点只可能取在每个点、两个点的中点，以及两对点垂直平分线的交点。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=50;

const double eps=1e-9;

inline int sgn(double x){

	if(x>eps)return 1;

	if(x<-eps)return -1;

	return 0;

}

struct P{

	double x,y;

	P(){}

	P(double _x,double _y){x=_x,y=_y;}

	P operator+(P b){return P(x+b.x,y+b.y);}

	P operator-(P b){return P(x-b.x,y-b.y);}

	P operator*(double b){return P(x*b,y*b);}

	P operator/(double b){return P(x/b,y/b);}

	void read(){scanf("%lf%lf",&x,&y);}

	double len(){return x*x+y*y;}

	double dis(const P&b){return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);}

	bool operator==(P b){return !sgn(x-b.x)&&!sgn(y-b.y);}

	P rot90(){return P(-y,x);}

}a[N],e[N*N][2];

int n,m,i,j,ans=N;

double d[N];

inline void solve(P O){

	//printf("%.10f %.10f\n",O.x,O.y);

	int i;

	for(i=1;i<=n;i++)d[i]=O.dis(a[i]);

	sort(d+1,d+n+1);

	int t=1;

	for(i=2;i<=n&&t<ans;i++)if(d[i]>d[i-1]+eps)t++;

	if(t<ans)ans=t;

}

inline void makeline(P a,P b){

	if(a==b)return;

	P c=(a+b)/2.0;

	solve(c);

	b=b-a;

	e[++m][0]=c;

	e[m][1]=c+b.rot90();

	//printf("%.5f %.5f %.5f %.5f\n",e[m][0].x,e[m][0].y,e[m][1].x,e[m][1].y);

}

inline double cross(P a,P b){

	return a.x*b.y-a.y*b.x;

}

inline void gao(P a,P b,P p,P q){

	double U=cross(p-a,q-p),D=cross(b-a,q-p);

	if(!sgn(D))return;

	//puts("!");

	solve(a+(b-a)*(U/D));

}

int main(){

	scanf("%d",&n);

	for(i=1;i<=n;i++)a[i].read();

	for(i=1;i<=n;i++)solve(a[i]);

	for(i=1;i<=n;i++)for(j=1;j<i;j++){

		makeline(a[i],a[j]);

	}

	//makeline(a[4],a[5]);

	//makeline(a[5],a[1]);

	for(i=1;i<=m;i++)for(j=1;j<i;j++)gao(e[i][0],e[i][1],e[j][0],e[j][1]);

	printf("%d",ans);

}

/*

6

0 -5

1 0

-1 0

2 3

3 2

-3 0

*/

G. Security Badge

对区间离散化，那么只需要检查$O(m)$个人是否可行，每次暴力Floodfill判断即可。

时间复杂度$O(m(n+m))$。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=10010;

int n,m,k,S,T,i,j,cnt,q[N],K;

int g[N],ed,v[N],vc[N],vd[N],nxt[N],vis[N],ans;

inline void add(int x,int y,int c,int d){

	v[++ed]=y;

	vc[ed]=c;

	vd[ed]=d;

	nxt[ed]=g[x];

	g[x]=ed;

}

void dfs(int x){

	if(vis[x])return;

	vis[x]=1;

	for(int i=g[x];i;i=nxt[i])if(vc[i]<=K&&K<=vd[i])dfs(v[i]);

}

int main(){

	scanf("%d%d%d%d%d",&n,&m,&k,&S,&T);

	for(i=1;i<=m;i++){

		int a,b,c,d;

		scanf("%d%d%d%d",&a,&b,&c,&d);

		add(a,b,c,d);

		q[++cnt]=c-1;

		q[++cnt]=d;

	}

	sort(q+1,q+cnt+1);

	for(i=2;i<=cnt;i++)if(q[i]!=q[i-1]){

		K=q[i];

		for(j=1;j<=n;j++)vis[j]=0;

		dfs(S);

		if(vis[T])ans+=q[i]-q[i-1];

	}

	printf("%d",ans);

}

H. Avoiding Airports

将每架飞机拆成上飞机和下飞机两个事件，并按照时间顺序依次考虑。

设$dp[x]$表示最后乘坐第$x$架飞机的最小代价，那么转移是经典斜率优化形式，对于每个点用单调队列维护凸壳即可。

时间复杂度$O(m\log m)$。

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int N=200010;

const ll inf=1LL<<60;

int n,m,i,e[N][4],cnt;

struct E{

	int x,y;

	E(){}

	E(int _x,int _y){x=_x,y=_y;}

}w[N<<1];

ll dp[N],ans=inf;

struct Line{

	ll k,b;

	Line(){}

	Line(ll _k,ll _b){k=_k,b=_b;}

	ll f(ll x){return k*x+b;}

};

vector<Line>g[N];

int head[N],tail[N],deg[N];

inline bool cmp(const E&a,const E&b){

	if(a.x!=b.x)return a.x<b.x;

	return a.y<b.y;

}

inline double pos(const Line&a,const Line&b){

	return 1.0*(a.b-b.b)/(b.k-a.k);

}

inline void ins(int o,ll k,ll b){

	if(b>=inf)return;

	Line now(k,b);

	int&h=head[o],&t=tail[o];

	if(h<=t){

		if(g[o][t].k==k){

			if(g[o][t].b<=b)return;

			t--;

		}

	}

	while(h<t&&pos(g[o][t-1],g[o][t])>=pos(g[o][t],now))t--;

	g[o][++t]=now;

}

inline ll cal(int o,ll x){

	int&h=head[o],&t=tail[o];

	if(h>t)return inf;

	while(h<t&&g[o][h].f(x)>g[o][h+1].f(x))h++;

	return g[o][h].f(x);

}

int main(){

	scanf("%d%d",&n,&m);

	for(i=1;i<=m;i++){

		scanf("%d%d%d%d",&e[i][0],&e[i][1],&e[i][2],&e[i][3]);

		deg[e[i][1]]++;

		w[++cnt]=E(e[i][2],-i);//s

		w[++cnt]=E(e[i][3],i);//e

	}

	sort(w+1,w+cnt+1,cmp);

	deg[1]++;

	for(i=1;i<=n;i++)tail[i]=-1,g[i].resize(deg[i]+2);

	ins(1,0,0);//kx+b

	for(i=1;i<=cnt;i++){

		int x=w[i].y;

		//printf("->%d %d\n",w[i].x,x);

		if(x<0){

			int y=-x;

			dp[y]=cal(e[y][0],e[y][2]);

			if(dp[y]<inf)dp[y]+=1LL*e[y][2]*e[y][2];

			//printf("! %d %lld\n",y,dp[y]);

		}else{

			//printf("ins %d %lld\n",e[x][1],dp[x]);

			ins(e[x][1],-2LL*e[x][3],dp[x]+1LL*e[x][3]*e[x][3]);

		}

	}

	for(i=1;i<=m;i++)if(e[i][1]==n)ans=min(ans,dp[i]);

	printf("%lld",ans);

}

/*

3 5

1 1 10 20

1 2 30 40

1 2 50 60

1 2 70 80

2 3 90 95

5 8

1 2 1 10

2 4 11 16

2 1 9 12

3 5 28 100

1 2 3 8

4 3 20 21

1 3 13 27

3 5 23 24

*/

I. Long Long Strings

初始串取字符集无穷的超长字符串是最坏情况，压缩区间后暴力操作即可。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 0, M = 0, Z = 1e9 + 7;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n;

const LL inf = 1e12;

struct A

{

	LL st;

	LL ed;

	LL stval;

	bool operator < (const A &b)const

	{

		return st < b.st;

	}

};

set<A>sot1, sot2;

void doit(set<A> &sot)

{

	char ch;

	while(~scanf(" %c", &ch))

	{

		if(ch == 'D')

		{

			LL pos;

			scanf("%lld", &pos);

			auto it = --sot.upper_bound({pos});

			LL st = it->st;

			LL ed = it->ed;

			LL stval = it->stval;

			sot.erase(it);

			vector<A>vt;

			if(st <= pos - 1)

			{

				vt.push_back({st, pos - 1, stval});

			}

			if(pos + 1 <= ed)

			{

				vt.push_back({pos, ed - 1, stval + pos + 1 - st});

			}

			for(auto w=sot.lower_bound({pos + 1}),nxt = w;w!= sot.end();w=nxt)

			{

				nxt = w; ++nxt;

				vt.push_back({w->st - 1, w->ed - 1, w->stval});

				sot.erase(w);

			}

			for(auto it : vt)sot.insert(it);

		}

		else if(ch == 'I')

		{

			char val_;

			LL pos, val;

			scanf("%lld %c", &pos, &val_);

			val = inf + val_;

			auto it = --sot.upper_bound({pos});

			LL st = it->st;

			LL ed = it->ed;

			LL stval = it->stval;

			sot.erase(it);

			vector<A>vt;

			if(st <= pos - 1)

			{

				vt.push_back({st, pos - 1, stval});

			}

			if(pos <= ed)

			{

				vt.push_back({pos + 1, ed + 1, stval + pos - st});

			}

			for(auto w=sot.lower_bound({pos + 1}),nxt = w;w!= sot.end();w=nxt)

			{

				nxt = w; ++nxt;

				vt.push_back({w->st + 1, w->ed + 1, w->stval});

				sot.erase(w);

			}

			vt.push_back({pos, pos, val});

			for(auto it : vt)sot.insert(it);

		}

		else break;

		/*

		for(auto it : sot)

		{

			printf("%lld %lld %lld\n", it.st, it.ed, it.stval);

		}

		puts("show end");

		*/

	}

}

bool check()

{

	LL ed1 = (--sot1.end())->ed;

	LL ed2 = (--sot1.end())->ed;

	if(ed1 != ed2)return 0;

	LL now = 1;

	while(now <= ed1)

	{

		auto it1 = sot1.begin();

		auto it2 = sot2.begin();

		LL ed1 = it1->ed;

		LL ed2 = it2->ed;

		if(it1->stval != it2->stval)return 0;

		LL stval = it1->stval;

		LL nxt = min(it1->ed, it2->ed) + 1;

		sot1.erase(it1);

		sot2.erase(it2);

		if(nxt <= ed1)

		{

			sot1.insert({nxt, ed1, nxt - now + stval});

		}

		if(nxt <= ed2)

		{

			sot2.insert({nxt, ed2, nxt - now + stval});

		}

		now = nxt;

	}

	return 1;

}

int main()

{

	sot1.clear();

	sot1.insert({1, inf, 1});

	sot2.clear();

	sot2.insert({1, inf, 1});

	doit(sot1);

	doit(sot2);

	/*

	for(auto it : sot1)

	{

		printf("%lld %lld %lld\n", it.st, it.ed, it.stval);

	}

	puts("-------------");

	for(auto it : sot2)

	{

		printf("%lld %lld %lld\n", it.st, it.ed, it.stval);

	}

	*/

	puts(check() ? "0" : "1");

	return 0;

}

/*

【trick&&吐槽】

【题意】

【分析】

【时间复杂度&&优化】

*/

J. Grid Coloring

设$f[i][j]$表示考虑前$i$行，第$i$行前$j$个都是蓝色，后面都是红色的方案数，暴力转移即可。

时间复杂度$O(n^3)$。

#include<cstdio>

typedef long long ll;

const int N=40;

int n,m,i,j,k;

ll ans,f[N][N];

char a[N][N];

bool can[N][N];

inline bool check(int x,int y){

	for(int i=1;i<=y;i++)if(a[x][i]=='R')return 0;

	for(int i=y+1;i<=m;i++)if(a[x][i]=='B')return 0;

	return 1;

}

int main(){

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;i++)scanf("%s",a[i]+1);

	for(i=1;i<=n;i++){

		for(j=0;j<=m;j++){

			can[i][j]=check(i,j);

		}

	}

	//f[i][j] [1..j] is B, j+1..m is R

	for(j=0;j<=m;j++)f[1][j]=can[1][j];

	for(i=1;i<n;i++)for(j=0;j<=m;j++)for(k=0;k<=j;k++)f[i+1][k]+=f[i][j]*can[i+1][k];

	for(j=0;j<=m;j++)ans+=f[n][j];

	printf("%lld",ans);

}

K. Spinning Up Palindromes

显然最优解中一定是从右往左操作，故问题可以转化成：给定数字$A$，找到一个数位和最小的数字$B$，使得$A+B$是回文串。

考虑从两边往中间DP，设$f[i][j][k]$表示考虑前后$i$个位置，前面希望后面进位为$j$，后面对前面进位为$k$的最小代价。

#include<cstdio>

#include<cstring>

const int N=50,inf=10000000;

int n,m,l,r,i,j,k,x,y,t,w;

char s[N];

int a[N],f[N][2][2],ans=inf;

inline void up(int&a,int b){a>b?(a=b):0;}

int main(){

	scanf("%s",s+1);

	n=strlen(s+1);

	for(i=1;i<=n;i++)a[i]=s[i]-'0';

	for(i=0;i<=n+5;i++)for(j=0;j<2;j++)for(k=0;k<2;k++)f[i][j][k]=inf;

	f[0][0][0]=f[0][1][0]=0;

	for(l=1,r=n;l<r;l++,r--)for(i=0;i<2;i++)for(j=0;j<2;j++)if(f[l-1][i][j]<inf){

		w=f[l-1][i][j];

		for(x=0;x<10;x++)for(y=0;y<10;y++){//what is b

			for(k=0;k<2;k++){//jinwei from l+1

				int A=a[l]+x+k,nA=0;

				if(A>=10)A-=10,nA++;

				if(nA!=i)continue;

				int B=a[r]+y+j,nB=0;

				if(B>=10)B-=10,nB++;

				if(A!=B)continue;

				up(f[l][k][nB],w+x+y);

			}

		}

	}

	m=n/2;

	if(n%2){

		for(i=0;i<2;i++)for(j=0;j<2;j++)if(f[m][i][j]<inf){

			w=f[m][i][j];

			for(x=0;x<10;x++){

				if((a[m+1]+x+j)/10!=i)continue;

				up(ans,w+x);

			}

		}

	}else{

		for(i=0;i<2;i++)for(j=0;j<2;j++)if(f[m][i][j]<inf){

			w=f[m][i][j];

			if(i==j)up(ans,w);

		}

	}

	printf("%d",ans);

}

L. Delayed Work

暴力枚举人数即可。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

ll K,P,X,i;double ans;

int main(){

	scanf("%lld%lld%lld",&K,&P,&X);

	ans=1e20;

	for(i=1;i<=3000000;i++){

		ans=min(ans,1.0*K*P/i+1.0*X*i);

	}

	printf("%.3f",ans);

}

M. Unsatisfying

若初始2-SAT无解，那么答案显然为$0$。

如果不存在$\neg x\lor\neg y$，那么无解。

否则枚举每个$x$，强行规定$x=true$，若2-SAT无解则答案为$1$。

否则答案只能为$2$。

时间复杂度$O(n(n+m))$。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 4010, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n, m, nn;

int x, y;

vector<int> a[N];

bool pick[N];

int sta[N], top;

bool dfs(int x)

{

	if(pick[x ^ 1]) return 0;

	if(pick[x]) return 1;

	pick[x] = 1;

	sta[++ top] = x;

	for(int i = a[x].size() - 1; ~ i; -- i){

		int y = a[x][i];

		if(!dfs(y)) return 0;

	}

	return 1;

}

bool solve()

{

	for(int i = 0; i < nn; i += 2) if(!pick[i] && !pick[i ^ 1]){

		top = 0;

		if(!dfs(i)){

			while(top) pick[sta[top --]] = 0;

			top = 0;

			if(!dfs(i ^ 1)) return 0;

		}

	}

	return 1;

}

int main()

{

	scanf("%d%d", &n, &m);

	int flag = 0;

	nn = n * 2;

	for(int i = 0; i < nn; i ++) pick[i] = 0, a[i].clear();

	for(int i = 1; i <= m; i ++){

		scanf("%d%d", &x, &y);

		int xx = abs(x), yy = abs(y);

		xx *= 2; yy *= 2;

		xx --; yy --;

		if(x < 0 && y < 0) flag = 1;

		if(x < 0 && y < 0){

			a[xx].push_back(yy ^ 1);

			a[yy].push_back(xx ^ 1);

			//printf("%d %d\n", xx, yy ^ 1);

			//printf("%d %d\n", yy, xx ^ 1);

		}

		else if(x < 0 && y > 0){

			a[xx].push_back(yy);

			a[yy ^ 1].push_back(xx ^ 1);

			//printf("%d %d\n", xx, yy);

			//printf("%d %d\n", yy ^ 1, xx ^ 1);

		}

		else if(x > 0 && y < 0){

			a[yy].push_back(xx);

			a[xx ^ 1].push_back(yy ^ 1);

			//printf("%d %d\n", yy, xx);

			//printf("%d %d\n", xx ^ 1, yy ^ 1);

		}

		else if(x > 0 && y > 0){

			a[xx ^ 1].push_back(yy);

			a[yy ^ 1].push_back(xx);

			//printf("%d %d\n", xx ^ 1, yy);

			//printf("%d %d\n", yy ^ 1, xx);

		}

	}

	if(!flag){puts("-1"); return 0;}

	if(!solve()) {puts("0"); return 0;}

	for(int i = 1; i <= n; i ++){

		for(int j = 0; j < nn; j ++){

			//a[i].clear();

			pick[j] = 0;

		}

		int xx = i * 2 - 1;

		//a[xx].push_back(xx ^ 1);

		a[xx ^ 1].push_back(xx);

		if(!solve()){

			puts("1"); return 0;

		}

		//a[xx].pop_back();

		a[xx ^ 1].pop_back();

	}

	puts("2");

	return 0;

}

/*

【trick&&吐槽】

【题意】

4 5

1 2

0 3

2 1

-1 -3

1 4

5 0

-2 3

3 5

4 2

3 -4

7 5

4 6

-2 -3

3 4

5 2

0

【分析】

【时间复杂度&&优化】

*/

巴特西

2017-2018 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

最新文章

热门文章