[BZOJ] 2303: [Apio 2011] 체크 염색 - 이소 & 병합
1920 단어 묘하다함께 조사하여 모으다
문제풀이
구역 내 에서 기수 차례 이상 을 연상시키고, 다시 병찰 판정 연통 추천 한 편 의 문제 풀이 로 바꾸다
코드
#include
#include
#include
#include
using namespace std;
#define fd(x) ((x)==1?1:(m+x-1))
const int N=1e6+10,mod=1e9;
typedef long long ll;
int n,m,K,a[N],b[N];
int f[N<<2],ss,pr=-1,lim,ans;
bool vs[N<<2],c[N];
char cp;
inline void rd(int &x)
{
cp=getchar();x=0;
for(;!isdigit(cp);cp=getchar());
for(;isdigit(cp);cp=getchar()) x=(x<<3)+(x<<1)+(cp^48);
}
int getfa(int x){return x==f[x]?x:f[x]=getfa(f[x]);}
void merge(int x,int y,int z)
{
if(z){
if(getfa(x)!=getfa(y+lim)) f[getfa(x)]=getfa(y+lim),ss--;
if(getfa(x+lim)!=getfa(y)) f[getfa(x+lim)]=getfa(y),ss--;
}
else{
if(getfa(x)!=getfa(y)) f[getfa(x)]=getfa(y),ss--;
if(getfa(x+lim)!=getfa(y+lim)) f[getfa(x+lim)]=getfa(y+lim),ss--;
}
}
inline int fp(int x,int y)
{
int re=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) re=(ll)re*x%mod;
return re;
}
inline void sol(int ty)
{
int i;lim=n+m-1;ss=lim<<1;
for(i=1;i<=ss;++i) f[i]=i;
for(i=1;i<=K;++i) if(a[i]!=1 || b[i]!=1){
if((!(a[i]&1))&&(!(b[i]&1))) merge(b[i],fd(a[i]),1^ty^c[i]);
else merge(b[i],fd(a[i]),ty^c[i]);
if(getfa(b[i])==getfa(b[i]+lim) || getfa(fd(a[i]))==getfa(fd(a[i])+lim)) return;
}
memset(vs,0,sizeof(vs));
ss--;vs[getfa(1)]=1;
for(i=1;i<=K;++i){
if(a[i]==1 && !vs[getfa(b[i])]) vs[getfa(b[i])]=1,ss--;
else if(b[i]==1 && !vs[getfa(fd(a[i]))]) vs[getfa(fd(a[i]))]=1,ss--;
}
ans+=fp(2,ss>>1);if(ans>=mod) ans-=mod;
}
int main(){
int i,x;
rd(n);rd(m);rd(K);
for(i=1;i<=K;++i){
rd(a[i]);rd(b[i]);rd(x);c[i]=x;
if(a[i]==1 && b[i]==1) pr=c[i]^1;
}
if(pr!=0) sol(0);
if(pr!=1) sol(1);
printf("%d",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ] 2303: [Apio 2011] 체크 염색 - 이소 & 병합전송문:bzoj2303 구역 내 에서 기수 차례 이상 을 연상시키고, 다시 병찰 판정 연통 추천 한 편 의 문제 풀이 로 바꾸다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.