2014-05-01

UVa 1417 - Traffic Jam

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

The kingdom of Tripbansai has an unusual traffic system. The city locations in the kingdom can be described as a grid and all the roads connect neighboring cities. This rectangular grid has 2 rows and C columns where every point represents a city. So there are 2 C cities and 3 C - 2 roads in this system.

Sometimes two adjacent cities become disconnected because of traffic jam, and sometimes the traffic problem has been solved so that a road can be usedd again. We can assume that every road is closed at first.

Ministry of Communications will give some instructions to you. Your task is to implement a program as a traffic response information system.

Each instruction appears as a single line in one ofthe formats below:

Close r1 c1 r2 c2 Close the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Open r1 c1 r2 c2 Open the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Ask r1 c1 r2 c2 Reply with Y if there exists a way from the city on (r1, c1) to the city on (r2, c2) ;
reply with N if there doesn’t.
Exit No more requests are forthcoming. The problem should exit.

Input

The first line ofthe input contains a single integer T (1$\le$T$\le$11) , representing the number of test cases that follow.

The first line of each test case consists of a single integer C (1$\le$C$\le$100000) , which is the number of columns.

There are some lines following, each for an instruction. Each test case ends with an instruction ``Exit”. There are no more than 100000 instructions in each test case. All the roads are closed initially, and each case is an independent problem.

Output

For each instruction Ask r1 c1 r2 c2, display a line containing Y or N.

Sample Input

3
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
3
Open 1 1 1 2
Ask 1 1 1 2
Close 1 1 1 2
Ask 1 1 1 2
Exit
2
Open 1 1 1 2
Open 1 2 2 2
Open 2 1 2 2
Ask 1 1 2 1
Exit

Sample Output

Y
N
Y
N
Y

Solution

題目描述：

對於一個 2 x C 的方格點來說，將會有 3 * C - 2 條邊。

題目解法：

維護一個區間角落四個點之間的連接資訊，也就是總共六種。

c[0] 左上右上
c[1] 左上右下
c[2] 左下右上
c[3] 左下右下
c[4] 左上左下
c[5] 右上右下

上方 r = 1 下方 r = 2 左方 c = left 右方 c = right

對於區間 [l, r] 我們只維護這個區間的資訊，不考慮繞此外的結果。
而對於區間的編號，由左而右，構成 0, 1, 2, 3, …, C，每一個可以看作是一個方格。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
struct Node {
    int c[6];
}; // - \ / _ | |
Node ST[262144 + 10];
void build(int k, int l, int r) {
    if(l > r)	return;
    if(l == r) {
        memset(&ST[k], 0, sizeof(ST[k]));
        return;
    }
    int mid = (l + r)/2;
    build(k<<1, l, mid);
    build(k<<1|1, mid+1, r);
}
Node combine(Node s1, Node s2) {
    Node s;
    s.c[0] = (s1.c[0] && s2.c[0]) || (s1.c[1] && s2.c[2]);
    s.c[1] = (s1.c[0] && s2.c[1]) || (s1.c[1] && s2.c[3]);
    s.c[2] = (s1.c[2] && s2.c[0]) || (s1.c[3] && s2.c[2]);
    s.c[3] = (s1.c[2] && s2.c[1]) || (s1.c[3] && s2.c[3]);
    s.c[4] = (s1.c[4]) || (s1.c[0] && s2.c[4] && s1.c[3]);
    s.c[5] = (s2.c[5]) || (s2.c[0] && s1.c[5] && s2.c[3]);
    return s;
}
void modify(int k, int l, int r, int qidx, int qfield, int qval) {
    if(l > r)	return;
    if(l == r) {
        ST[k].c[qfield] = qval;
        ST[k].c[1] = (ST[k].c[0] && ST[k].c[5]) || (ST[k].c[3] && ST[k].c[4]);
        ST[k].c[2] = (ST[k].c[0] && ST[k].c[4]) || (ST[k].c[3] && ST[k].c[5]);
        return;
    }
    int mid = (l + r)/2;
    if(qidx > mid)
        modify(k<<1|1, mid+1, r, qidx, qfield, qval);
    else
        modify(k<<1, l, mid, qidx, qfield, qval);
    ST[k] = combine(ST[k<<1], ST[k<<1|1]);
}
Node query(int k, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr)
        return ST[k];
    int mid = (l + r)/2;
    if(ql > mid)
        return query(k<<1|1, mid+1, r, ql, qr);
    else if(qr <= mid)
        return query(k<<1, l, mid, ql, qr);
    else
        return combine(query(k<<1, l, mid, ql, qr), 
                        query(k<<1|1, mid+1, r, ql, qr));
}
int main() {
    int testcase, C;
    int r1, r2, c1, c2;
    int lines = 0;
    char cmd[10];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &C);
        memset(ST, 0, sizeof(ST));
        build(1, 0, C);
        while(scanf("%s", cmd) == 1 && cmd[0] != 'E') {
            scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            if(cmd[0] == 'O' || cmd[0] == 'C') { // open
                int qval = cmd[0] == 'O' ? 1 : 0;
                if(c1 != c2) {
                    modify(1, 0, C, min(c1, c2), r1 == 1 ? 0 : 3, qval);
                } else {
                    modify(1, 0, C, min(c1, c2) - 1, 5, qval);
                    modify(1, 0, C, min(c1, c2), 4, qval);
                }
            } else {
                if(c1 > c2) {
                    swap(c1, c2);
                    swap(r1, r2);
                }
                if(r1 == r2 && c1 == c2) {
                    puts("Y");
                } else if(r1 != r2 && c1 == c2) {
                    Node l = query(1, 0, C, 0, c1 - 1);
                    Node r = query(1, 0, C, c1, C);
                    if(l.c[5] || r.c[4])
                        puts("Y");
                    else
                        puts("N");
                } else {
                    Node l = query(1, 0, C, 0, c1 - 1);
                    Node r = query(1, 0, C, c2, C);
                    Node m = query(1, 0, C, c1, c2 - 1);
                    int kc[2][2] = { {0, 1}, {2, 3} };
                    if(m.c[kc[r1 - 1][r2 - 1]] || 
                        (l.c[5] && m.c[kc[(3 - r1) - 1][r2 - 1]]) ||
                        (r.c[4] && m.c[kc[r1 - 1][(3 - r2) - 1]]) ||
                        (l.c[5] && r.c[4] && m.c[kc[(3 - r1) - 1][(3 - r2) - 1]]))
                        puts("Y");
                    else
                        puts("N");
                }
            }
        }
    }
    return 0;
}

Morris' Blog