[NOIP 2015 시 뮬 레이 션 11.3] IOIOI 카드 점

Description
네가 본 제목 처럼 지금 은 A 개의 I 가 있 고 B 개의 O 에 이 어 C 개의 I 에 이 어 D 개의 O 에 이 어 E 개의 I 에 이 어 한 줄 로 서 있다.당신 은 지금 N 가지 조작 이 있 습 니 다. i 번 째 조작 이 있 습 니 다. li 번 째 문자 부터 ri 번 째 문자 까지 이 구간 의 문자, I 는 O, O 는 I 가 되 고 시간 은 ri - li + 1 입 니 다.모든 문 자 를 I 의 최소 시간 으로 바 꿔 주세요.풀 리 지 않 으 면 출력 - 1.A,B,C,D,E,N<=10^5
Solution
신기 한 문제.먼저%% 출제 자, 이런 생각 을 누가 얻 고 싶 어 요 ~ Japanese... 우선, 우 리 는 새로운 서열 b, bi = ai ^ ai + 1 을 만 들 었 습 니 다. 이렇게 b 중 에 0 이 쌓 였 고 중간 에 4 개 1 이 있 습 니 다.그렇다면 한 번 의 조작 은 무엇 에 해당 합 니까?bl - 1 과 br 를 반대 하 는 것 과 같 습 니 다!(왜 그런 지 생각해 보 세 요) 그러면 우 리 는 l - 1 에서 r 로 길 이 를 r - l + 1 의 변 으로 연결 할 수 있 습 니 다.그리고 우리 의 임 무 는 b 서열 을 0 으로 바 꾸 는 것 이 되 었 다.(왜 그런 지 생각해 보 세 요) 그러면 우 리 는 spfa / 디 제 스 트 라 만 때 리 면 됩 니 다.하지만 동 나리 의 테스트 를 통 해 디 제 스 트 라 는 넘 지 못 할 것 같 습 니 다.
Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 500005
#define ll long long
using namespace std;
int n,tot,g[3][4]={0,1,2,3,0,2,1,3,0,3,1,2};
int t[N*2],next[N*2],last[N],a[5],d[N*2];
ll dis[N],v[N*2],ans,l,r;
bool bz[N];
void add(int x,int y,ll z){
    t[++tot]=y;v[tot]=z;next[tot]=last[x];last[x]=tot;
}
ll spfa(int S,int T) {
    memset(dis,127,sizeof(dis));
    ll mx=dis[S];dis[S]=0;
    memset(bz,0,sizeof(bz));bz[S]=1;
    int i=0,j=1;d[1]=S;
    while (i<j) {
        rep(k,d[++i]) if (dis[t[k]]>dis[d[i]]+v[k]) {
            dis[t[k]]=dis[d[i]]+v[k];
            if (!bz[t[k]]) bz[t[k]]=1,d[++j]=t[k];
        }
        bz[d[i]]=0;
    }
    if (dis[T]==mx) return -1;else return dis[T];
} 
int main() {
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    fo(i,0,4) scanf("%d",&a[i]),a[i]+=a[i-1];
    scanf("%d",&n);ans=100000000000;
    fo(i,1,n) scanf("%lld%lld",&l,&r),add(l-1,r,r-l+1),add(r,l-1,r-l+1);
    fo(i,0,2) {
        ll x=spfa(a[g[i][0]],a[g[i][1]]),y=spfa(a[g[i][2]],a[g[i][3]]);
        if (x==-1||y==-1) continue;
        ans=min(ans,x+y);
    }
    if (ans==100000000000) printf("-1");else printf("%lld",ans);
}