Submission #11556

#	Time	Username	Problem	Language	Result	Execution time	Memory
11556		gs12117	전선 연결하기 (GA9_wire)	C++98	100 / 100	312 ms	27508 KiB

wire

#include<stdio.h>
int n;
int a[600100];
int b[300100][2];
int chk[300100];
int uft[300100][2];
int it[1<<21];
int itm[1<<21];
int flag;
int uftf(int x){
    if(uft[x][0]==x)return x;
    uftf(uft[x][0]);
    uft[x][1]^=uft[uft[x][0]][1];
    return uft[x][0]=uft[uft[x][0]][0];
}
void push(int loc,int val){
    loc+=1<<20;
    itm[loc]=1;
    while(loc!=0){
        it[loc]=val;
        loc/=2;
    }
}
void pop(int loc){
    loc+=1<<20;
    it[loc]=0;
    loc/=2;
    while(loc!=0){
        if(it[loc*2]!=0)it[loc]=it[loc*2];
        else it[loc]=it[loc*2+1];
        loc/=2;
    }
}
void link(int pa,int pb,int val){
    if(uftf(pa)==uftf(pb)){
        if((uft[pa][1]^uft[pb][1])!=val)flag=1;
    }
    else{
        uft[uft[pb][0]][1]=(val^uft[pa][1]^uft[pb][1]);
        uft[uft[pb][0]][0]=uft[pa][0];
    }
}
void merge(int loc){
    if(it[loc]==0||itm[loc]==1)return;
    merge(loc*2);
    merge(loc*2+1);
    itm[loc]=1;
    if(it[loc*2]!=0&&it[loc*2+1]!=0){
        link(it[loc*2],it[loc*2+1],0);
    }
}
void calc(int start,int end,int p){
    start+=1<<20;
    end+=1<<20;
    while(start<=end){
        if(start%2==1){
            merge(start);
            if(it[start]!=0)link(p,it[start],1);
            start++;
        }
        if(end%2==0){
            merge(end);
            if(it[end]!=0)link(p,it[end],1);
            end--;
        }
        start/=2;
        end/=2;
    }
}
int main(){
    int i;
    scanf("%d",&n);
    for(i=0;i<2*n;i++){
        scanf("%d",&a[i]);
        b[a[i]][chk[a[i]]]=i;
        chk[a[i]]++;
    }
    for(i=1;i<=n;i++){
        uft[i][0]=i;
        uft[i][1]=0;
    }
    for(i=1;i<=n;i++){
        push(b[i][0],i);
    }
    flag=0;
    for(i=0;i<2*n;i++){
        if(b[a[i]][1]==i){
            pop(b[a[i]][0]);
            calc(b[a[i]][0],b[a[i]][1],a[i]);
        }
    }
    if(flag==1){
        printf("IMPOSSIBLE");
    }
    else{
        for(i=1;i<=n;i++){
            uftf(i);
        }
        for(i=0;i<2*n;i++){
            if(uft[a[i]][1]==0)printf("^");
            else printf("v");
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 37 / 37
• Subtask 4: 39 / 39