BZOJ 1018: [SHOI2008]堵塞的交通traffic

正文索引 [隐藏]

Input
Output
Sample Input
Sample Output
题解
代码
数据>.<好孩子看不见

Description

有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个城市和3C-2条道路。小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式： Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了； Open r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了； Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N；

Input

第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。对30%测试数据，我们保证C小于等于1000，信息条数小于等于1000；对100%测试数据，我们保证 C小于等于100000，信息条数小于等于100000。

Output

对于每个查询，输出一个“Y”或“N”。

Sample Input

2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit

Sample Output

Y
N

题解

Orz 这种题目、、、、、、、、、把情况分清楚就行了，不仅要讨论通过中间联通的，还有讨论通过一边或者两边才能联通的。

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=100010;
int n;
struct State{
    bool lr[2][2];
    bool ll,rr;
    State(){
        memset(lr,false,sizeof(lr));ll=rr=false;
    }
};
struct Btree{
    int left,right;
    State sta;
};
Btree tree[Maxn*4+5];
bool up[Maxn],bom[Maxn],cen[Maxn];
void build(int x,int left,int right){
    tree[x].left=left;
    tree[x].right=right;
    if (left==right){
    }else{
        int mid=(left+right)/2;
        build(x*2,left,mid);
        build(x*2+1,mid+1,right);
    }
}
inline State mergeState(State left,State right){
    State ans;
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            for (int k=0;k<2;k++){
                ans.lr[i][j]=ans.lr[i][j]
                            || (left.lr[i][k] && right.lr[k][j])
                            || (left.lr[i][k] && right.lr[k^1][j] && (left.rr || right.ll));
            }
        }
    }
    ans.ll=left.ll;
    ans.rr=right.rr;
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            ans.ll=ans.ll || (left.lr[i][j] && left.lr[i^1][j^1] && (left.rr || right.ll));
            ans.rr=ans.rr || (right.lr[i][j] && right.lr[i^1][j^1] && (left.rr || right.ll));
        }
    }
    return ans;
}
void Change(int x,int pos){
    if (pos<1 || pos>n-1) return;
    if (tree[x].left==tree[x].right){
        State tmp;
        tmp.ll=cen[pos] || (up[pos] && bom[pos] && cen[pos+1]);
        tmp.rr=cen[pos+1] || (up[pos] && bom[pos] && cen[pos]);
        tmp.lr[0][0]=up[pos] || (bom[pos] && cen[pos] && cen[pos+1]);
        tmp.lr[0][1]=(up[pos] && cen[pos+1]) || (bom[pos] && cen[pos]);
        tmp.lr[1][1]=bom[pos] || (up[pos] && cen[pos] && cen[pos+1]);
        tmp.lr[1][0]=(up[pos] && cen[pos]) || (bom[pos] && cen[pos+1]);
        tree[x].sta=tmp;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (pos<=mid) Change(x*2,pos);
        if (mid<pos) Change(x*2+1,pos);
        tree[x].sta=mergeState(tree[x*2].sta,tree[x*2+1].sta);
    }
}
State Query(int x,int left,int right){
    if (left>right) return State();
    if (left<=tree[x].left && tree[x].right<=right){
        return tree[x].sta;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (right<=mid) return Query(x*2,left,right);
        if (left>mid) return Query(x*2+1,left,right);
        return mergeState( Query(x*2,left,right) , Query(x*2+1,left,right) );
    }
}
inline int remin(int a,int b){
    if (a<b)return a;
    return b;
}
inline void swap(int &a,int &b){
    int c=a;a=b;b=c;
}
int main(){
    freopen("traffic.in","r",stdin);
    freopen("traffic.out","w",stdout);
    scanf("%d",&n);
    build(1,1,n);
    char str[10];int x1,x2,y1,y2;
    while (true){
        scanf("%s",&str);
        if (str[0]=='E') return 0;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1--;x2--;
        if (str[0]=='O'){
            if (y1==y2)
                cen[y1]=true;
            else{
                if (x1==0)
                    up[remin(y1,y2)]=true;
                else
                    bom[remin(y1,y2)]=true;
            }
            Change(1,remin(y1,y2)-1);
            Change(1,remin(y1,y2));
        }
        if (str[0]=='C'){
            if (y1==y2)
                cen[y1]=false;
            else{
                if (x1==0)
                    up[remin(y1,y2)]=false;
                else
                    bom[remin(y1,y2)]=false;
            }
            Change(1,remin(y1,y2)-1);
            Change(1,remin(y1,y2));
        }
        if (str[0]=='A'){
            if (x1==x2 && y1==y2){
                printf("Y\n");continue;
            }
            if (y1==y2){
                printf( (Query(1,1,y1-1).rr || Query(1,y1,n-1).ll)?"Y\n":"N\n" );
                continue;
            }
            if (y1>y2) {swap(y1,y2);swap(x1,x2);}
            State ls=Query(1,1,y1-1);
            State rs=Query(1,y2,n-1);
            State ms=Query(1,y1,y2-1);
            //printf("Assert ->%d %d\n",Query(1,1,1).ll,Query(1,1,1).rr);
            bool ans=ms.lr[x1][x2];
            ans=ans || (ms.ll && ms.lr[x1^1][x2]);
            ans=ans || (ms.rr && ms.lr[x1][x2^1]);
            ans=ans || (ms.ll && ms.rr && ms.lr[x1^1][x2^1]);
            ans=ans || (ls.rr && ms.lr[x1^1][x2]);
            ans=ans || (rs.ll && ms.lr[x1][x2^1]);
            ans=ans || (ls.rr && ms.lr[x1^1][x2^1] && rs.ll);
            printf( ans?"Y\n":"N\n" );
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include<cstdio>

#include<cstring>

using namespace std;

const int Maxn=100010;

int n;

struct State{

bool lr[2][2];

bool ll,rr;

State(){

memset(lr,false,sizeof(lr));ll=rr=false;

}

};

struct Btree{

int left,right;

State sta;

};

Btree tree[Maxn*4+5];

bool up[Maxn],bom[Maxn],cen[Maxn];

void build(int x,int left,int right){

tree[x].left=left;

tree[x].right=right;

if (left==right){

}else{

int mid=(left+right)/2;

build(x*2,left,mid);

build(x*2+1,mid+1,right);

}

inline State mergeState(State left,State right){

State ans;

for (int i=0;i<2;i++){

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

for (int k=0;k<2;k++){

ans.lr[i][j]=ans.lr[i][j]

|| (left.lr[i][k] && right.lr[k][j])

|| (left.lr[i][k] && right.lr[k^1][j] && (left.rr || right.ll));

}

ans.ll=left.ll;

ans.rr=right.rr;

for (int i=0;i<2;i++){

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

ans.ll=ans.ll || (left.lr[i][j] && left.lr[i^1][j^1] && (left.rr || right.ll));

ans.rr=ans.rr || (right.lr[i][j] && right.lr[i^1][j^1] && (left.rr || right.ll));

}

return ans;

}

void Change(int x,int pos){

if (pos<1 || pos>n-1) return;

if (tree[x].left==tree[x].right){

State tmp;

tmp.ll=cen[pos] || (up[pos] && bom[pos] && cen[pos+1]);

tmp.rr=cen[pos+1] || (up[pos] && bom[pos] && cen[pos]);

tmp.lr[0][0]=up[pos] || (bom[pos] && cen[pos] && cen[pos+1]);

tmp.lr[0][1]=(up[pos] && cen[pos+1]) || (bom[pos] && cen[pos]);

tmp.lr[1][1]=bom[pos] || (up[pos] && cen[pos] && cen[pos+1]);

tmp.lr[1][0]=(up[pos] && cen[pos]) || (bom[pos] && cen[pos+1]);

tree[x].sta=tmp;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (pos<=mid) Change(x*2,pos);

if (mid<pos) Change(x*2+1,pos);

tree[x].sta=mergeState(tree[x*2].sta,tree[x*2+1].sta);

}

State Query(int x,int left,int right){

if (left>right) return State();

if (left<=tree[x].left && tree[x].right<=right){

return tree[x].sta;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (right<=mid) return Query(x*2,left,right);

if (left>mid) return Query(x*2+1,left,right);

return mergeState( Query(x*2,left,right) , Query(x*2+1,left,right) );

}

inline int remin(int a,int b){

if (a<b)return a;

return b;

}

inline void swap(int &a,int &b){

int c=a;a=b;b=c;

}

int main(){

freopen("traffic.in","r",stdin);

freopen("traffic.out","w",stdout);

scanf("%d",&n);

build(1,1,n);

char str[10];int x1,x2,y1,y2;

while (true){

scanf("%s",&str);

if (str[0]=='E') return 0;

scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

x1--;x2--;

if (str[0]=='O'){

if (y1==y2)

cen[y1]=true;

else{

if (x1==0)

up[remin(y1,y2)]=true;

else

bom[remin(y1,y2)]=true;

}

Change(1,remin(y1,y2)-1);

Change(1,remin(y1,y2));

}

if (str[0]=='C'){

if (y1==y2)

cen[y1]=false;

else{

if (x1==0)

up[remin(y1,y2)]=false;

else

bom[remin(y1,y2)]=false;

}

Change(1,remin(y1,y2)-1);

Change(1,remin(y1,y2));

}

if (str[0]=='A'){

if (x1==x2 && y1==y2){

printf("Y\n");continue;

}

if (y1==y2){

printf( (Query(1,1,y1-1).rr || Query(1,y1,n-1).ll)?"Y\n":"N\n" );

continue;

}

if (y1>y2) {swap(y1,y2);swap(x1,x2);}

State ls=Query(1,1,y1-1);

State rs=Query(1,y2,n-1);

State ms=Query(1,y1,y2-1);

//printf("Assert ->%d %d\n",Query(1,1,1).ll,Query(1,1,1).rr);

bool ans=ms.lr[x1][x2];

ans=ans || (ms.ll && ms.lr[x1^1][x2]);

ans=ans || (ms.rr && ms.lr[x1][x2^1]);

ans=ans || (ms.ll && ms.rr && ms.lr[x1^1][x2^1]);

ans=ans || (ls.rr && ms.lr[x1^1][x2]);

ans=ans || (rs.ll && ms.lr[x1][x2^1]);

ans=ans || (ls.rr && ms.lr[x1^1][x2^1] && rs.ll);

printf( ans?"Y\n":"N\n" );

}

return 0;

}

数据>.<好孩子看不见

链接: http://pan.baidu.com/s/1sj5FtWL 密码: e9zt

WNJXYKの博客

喂你脚下有坑