Connect [Richard Peng, 2007]

It's a fairly well-known fact that Canada has two seasons: winter and road construction. In the good old days before global warming, road construction season was July while winter was the other 11 months. As the earth got warmer, road construction season now runs April through September. This is bad news for all the moose who use the road network as their main method of transportation since their road usage is now disrupted by road construction for six months rather than one. Canmuu The Canadian Moose wants to build a travel scheduling system that knows the status of all roads and can tell moose whether they could possibly travel between cities by only taking the roads. Being a bit dimwitted, moose will travel only roads that fall inclusively in the range of columns bounded by the starting and ending cities. Canmuu has noticed that all of the important road junctions (usually cities) in Canada can be described as a grid and furthermore all the roads connect neighboring points -- and only neighboring points -- in the grid. He has drawn a rectilinear grid of R (1 <= R <= 2) rows and C (1 <= C <= 15,000) columns where every point on the grid represents a road junction. The following is an example of such a grid for Southern Ontario (the *'s represent unconnected, empty locations, i.e., farms): * Orangeville---Barrie------Peterborough * | | Waterloo--Mississauga---Toronto--------Lindsey-------Kingston In this example, although a path exists between Waterloo and Orangeville, no acceptable path exists as the moose must go through Toronto. If the road between Lindsey and Kingston is closed down, it's no longer possible to travel from Waterloo to Kingston (or from anywhere to Kingston). But if the road from Toronto to Lindsey is closed down instead, it is still be possible to travel from Waterloo to Kingston. For easy reference, cities are denoted as row,column so the map above becomes: 1,1 1,2------1,3------1,4 1,5 | | 2,1------2,2------2,3------2,4------2,5 Canmuu has created a network that supplies real-time instructions to a Moose Travel Scheduler. He even designed a system to inform the scheduler of the N roads that already exist; they are in the input file (see the description below). The real-time instructions appear as single lines of input on the 'standard input' device, often known as the 'console'. Each line has one of the formats below: C r1 c1 r2 c2 The road connecting adjacent points r1,c1 to r2,c2 is closed for maintenance. O r1 c1 r2 c2 The road between adjacent points r1,c1 and r2,c2 is now open. This could either mean either a new road has been constructed or road maintenance on an existing road has been finished. T r1 c1 r2 c2 A moose wants to travel only on roads from potentially non-adjacent points r1,c1 to r2,c2 using a path that does not go outside columns c1 and c2: reply with Y if he can; reply with N if he cannot. E No more requests are forthcoming; the scheduler program should exit. Implement a program to read the initial road network and calculate the answers to as many as 50,000 requests as they appear. Your scheduling program will conduct a dialog with the 'reactive' grading program: * Read lines in the format described above (there is no need to acknowledge 'C' or 'O' requests) * Print a single character on a line by itself to standard output when requested to do so by the 'T' directive * Exit your program after reading the 'E' line Interactive programs usually require extra code that causes output to be unbuffered -- to be written in real time instead of buffering for faster (but later) output. Those C/C++ users who use #include <stdio.h> should execute this line before any input or output: setlinebuf (stdout); Users of <stdio.h> should also use fgets () to read from stdin. Use of scanf is not recommended; do something like this to parse input data: char line[1000]; setlinebuf (stdout); fgets (line, 1000, stdin); sscanf ("..format..", &var1, ...); Those C++ users who use iostream should cout << flush after each line (and also use cin in the normal manner): cout << answer << endl; cout << flush; Java users should use the following output scheme for output: import java.io.*; ... PrintStream out = new PrintStream (System.out, true); // 'unbuffers' output ... out.println (answer); Here's a sample dialog for the map above. The lines with "<-" are lines that are data going to your program; lines with "->" are output from you program to standard output (the console). Of course, the little arrows do not appear in the actual input file; neither does the explanatory text. <- C 2 4 2 5 <-- The road connecting 2,4 and 2,5 is closed <- T 2 1 2 5 <-- A moose wishes to travel from 2,1 to 2,5 -> N <-- But that's not possible with the roads as they stand <- T 2 1 1 2 <-- A moose wishes to travel from 2,1 to 1,2 -> N <-- There is a path, but it's unacceptable in moose terms <- C 2 3 2 4 <-- The road connecting 2,3 and 2,4 is closed <- O 2 4 2 5 <-- The road connecting 2,4 and 2,5 is now open <- T 2 1 2 5 <-- A moose wishes to travel from 2,1 to 2,5 -> Y <-- Which is possible <- E <-- time to exit Time limit for each test case: 1.60 CPU seconds PROBLEM NAME: connect INPUT FORMAT: * Line 1: A single integer: N * Lines 2..N+1: Line i+1 describes a road in place using four space-separated integers which are respectively the row,column coordinates of two connected cities: r1, c1, r2, and c2. There are no duplicates in this list. SAMPLE INPUT (file connect.in): 8 1 2 1 3 1 3 1 4 1 3 2 3 1 4 2 4 2 1 2 2 2 2 2 3 2 3 2 4 2 4 2 5 INPUT DETAILS: Same as the road map described in the problem OUTPUT FORMAT: No lines are written to the output file. SAMPLE OUTPUT (file connect.out): [empty file]
ქართული თარგმანი არ არის დამატებული

connect

This problem is essentially dynamic connectivity on a grid graphs. The O(log^2V) solution for general dynamic connectivity might be modified to solve this problem, but was not considered to be a feasible solution due to the long code length. Here is a solution that performs the operations in O(RlogC) time per operation for general grid graphs: Consider blocks of 2^k columns at a time. For each 'block', we track 2R 'points', namely the vertices on each end of the columns. Then when we merge two blocks whos end columns are adjacent, it suffices to do a flood-fill on the vertices, which can be done in O(R) time. Now we keep all the 'blocks' for the columns in the form of a range tree. When we change an edge, all we have to do is update the O(logC) blocks that contain that edge. When we want the connectivity of an entire segment, we can merge O(logC) segments together. Therefore, this algorithm supports all operations in O(RlogC) time. Since R=2, the operations can be sped up even further by using bit-operations. This only might be an issue on case 9. The test data were generated as follows: First 7 cases were made with 1/2 of the instructions being T while C and O take up 1/4 respectively. Cases 8-10 were generated with T instructions taking up 3/4 and the rest split between T and C. Furthermore, the queries for the last 3 cases were generated with maximizing the column span in mind. In cases 5-10, the edges are inserted/deleted via. a stack (which might be problematic again codes that look back a bit) and the data were designed so large chunks are connected/disconnected frequently. The road networks in cases 4-9 are of the maximum size. To lower the implementation difficulty, only 15,000 instructions are used in case 4-7 while case 9 was the only case at maximum size. Cases 2-4: Randomly generated test cases with specified density. These are meant to be the 'easy' data. Case 5: R=1, all the roads are on a single line. This is the 'motivation' for the solution algorithm. Case 6: R=2, a 'slanted' binary tree with the first line being the main branch. This is a generalization of case 5. Case 8: The graph is the form of a cycle and all queries are concerning the connectivity of (1,1) and (2,C). Case 8: A forest of trees where each node's ancestor is on the previous column. Case 9: Row 1 are 2 has all the edges. Vertical edges between the two rows are inserted/deleted randomly. A solution based on flood-fill is expected to get cases 1-4 while the full O(RlogC) solution is needed for cases 5-9. Clever hacks based on iterating through the two columns and track things using binary numbers might be able to get another 2-4 of the cases. Below is the solution of China's Yucheng Zhang: #include <cstring> using namespace std; inline void swap(int& a, int& b) { int tmp = a; a = b; b = tmp; } const int Blocksize = 100; const int Blockn = 15000 / Blocksize; int G[15000][3]; int block[Blockn][2][2]; int changed[Blockn]; inline void setg(int r1, int c1, int r2, int c2, int x) { if (c1 == c2) G[c1][2] = x; else { if (c1 > c2) swap(c1, c2); G[c1][r1] = x; } changed[c1 / Blocksize] = true; } inline void process(int start, int end, int& m1, int& m2) { for (int i = start; i < end; i++) { if (!m1 && !m2) break; if (G[i][2] && (m1 || m2)) m1 = m2 = 1; if (!G[i][0]) m1 = 0; if (!G[i][1]) m2 = 0; } } inline void makeblock(int x) { int start = Blocksize * x; int end = Blocksize * (x + 1); for (int t = 0; t < 2; t++) { int m1, m2; m1 = m2 = 0; if (!t) m1 = 1; else m2 = 1; process(start, end, m1, m2); block[x][t][0] = m1; block[x][t][1] = m2; } changed[x] = false; } inline bool answer(int r1, int c1, int r2, int c2) { if (c1 > c2) { swap(r1, r2); swap(c1, c2); } int b1 = c1 / Blocksize; int b2 = c2 / Blocksize; int m1, m2; m1 = m2 = 0; if (!r1) m1 = 1; else m2 = 1; if (b1 == b2) { process(c1, c2, m1, m2); } else { process(c1, (b1 + 1) * Blocksize, m1, m2); if (!m1 && !m2) return false; for (int i = b1 + 1; i < b2; i++) { if (changed[i]) makeblock(i); int newm1 = 0, newm2 = 0; if (m1 && block[i][0][0]) newm1 = 1; if (m1 && block[i][0][1]) newm2 = 1; if (m2 && block[i][1][0]) newm1 = 1; if (m2 && block[i][1][1]) newm2 = 1; m1 = newm1; m2 = newm2; if (!m1 && !m2) return false; } process(b2 * Blocksize, c2, m1, m2); } if (G[c2][2] && (m1 || m2)) m1 = m2 = 1; if ((r2 == 0 && m1) || (r2 == 1 && m2)) return true; else return false; } char line[100]; inline void solve() { while (1) { fgets(line, 100, stdin); if (line[0] == 'E') break; char cmd; int r1, c1, r2, c2; sscanf(line, "%c%d%d%d%d", &cmd, &r1, &c1, &r2, &c2); r1--; c1--; r2--; c2--; if (cmd == 'C') setg(r1, c1, r2, c2, 0); else if (cmd == 'O') setg(r1, c1, r2, c2, 1); else { bool ans = answer(r1, c1, r2, c2); if (ans) printf("Y\n"); else printf("N\n"); } } } inline void init() { memset(G, 0, sizeof G); for (int i = 0; i < Blockn; i++) changed[i] = true; FILE* fin = fopen("connect.in", "r"); int N; fscanf(fin, "%d", &N); for (int i = 0; i < N; i++) { int r1, c1, r2, c2; fscanf(fin, "%d%d%d%d", &r1, &c1, &r2, &c2); r1--; c1--; r2--; c2--; setg(r1, c1, r2, c2, 1); } } int main() { setlinebuf(stdout); init(); solve(); return 0; }

Below is the solution of China's Yucheng Zhang

#include <cstring>
using namespace std;

inline void swap(int& a, int& b) { int tmp = a; a = b; b = tmp; }

const int Blocksize = 100;
const int Blockn = 15000 / Blocksize;

int G[15000][3];
int block[Blockn][2][2];
int changed[Blockn];

inline void setg(int r1, int c1, int r2, int c2, int x) {
    if (c1 == c2) G[c1][2] = x;
    else {
        if (c1 > c2) swap(c1, c2);
        G[c1][r1] = x;
    }
    changed[c1 / Blocksize] = true;
}

inline void process(int start, int end, int& m1, int& m2) {
    for (int i = start; i < end; i++) {
        if (!m1 && !m2) break;
        
        if (G[i][2] && (m1 || m2)) m1 = m2 = 1;
        if (!G[i][0]) m1 = 0;
        if (!G[i][1]) m2 = 0;
    }
}

inline void makeblock(int x) {
    int start = Blocksize * x;
    int end = Blocksize * (x + 1);
    
    for (int t = 0; t < 2; t++) {
        int m1, m2;
        m1 = m2 = 0;
        if (!t) m1 = 1; else m2 = 1;
        
        process(start, end, m1, m2);
        
        block[x][t][0] = m1;
        block[x][t][1] = m2;
    }
    
    changed[x] = false;
}

inline bool answer(int r1, int c1, int r2, int c2) {
    if (c1 > c2) {
        swap(r1, r2);
        swap(c1, c2);
    }
    
    int b1 = c1 / Blocksize;
    int b2 = c2 / Blocksize;
    
    int m1, m2;
    m1 = m2 = 0;
    if (!r1) m1 = 1; else m2 = 1;
    
    if (b1 == b2) {
        process(c1, c2, m1, m2);
    } else {
        process(c1, (b1 + 1) * Blocksize, m1, m2);
        if (!m1 && !m2) return false;
        
        for (int i = b1 + 1; i < b2; i++) {
            if (changed[i]) makeblock(i);
            
            int newm1 = 0, newm2 = 0;
            if (m1 && block[i][0][0]) newm1 = 1;
            if (m1 && block[i][0][1]) newm2 = 1;
            if (m2 && block[i][1][0]) newm1 = 1;
            if (m2 && block[i][1][1]) newm2 = 1;
            
            m1 = newm1; m2 = newm2;
            if (!m1 && !m2) return false;
        }
        
        process(b2 * Blocksize, c2, m1, m2);
    }
        
    if (G[c2][2] && (m1 || m2)) m1 = m2 = 1;
    
    if ((r2 == 0 && m1) || (r2 == 1 && m2)) return true;
    else return false;
}

char line[100];
inline void solve() {
    while (1) {
        fgets(line, 100, stdin);
        if (line[0] == 'E') break;
        
        char cmd; int r1, c1, r2, c2;
        sscanf(line, "%c%d%d%d%d", &cmd, &r1, &c1, &r2, &c2);
        r1--; c1--; r2--; c2--;
        
        if (cmd == 'C') setg(r1, c1, r2, c2, 0);
        else if (cmd == 'O') setg(r1, c1, r2, c2, 1);
        else {
            bool ans = answer(r1, c1, r2, c2);
            if (ans) printf("Y\n"); else printf("N\n");
        }
    }
}

inline void init() {
    memset(G, 0, sizeof G);
    for (int i = 0; i < Blockn; i++) changed[i] = true;
    
    FILE* fin = fopen("connect.in", "r");
    int N; fscanf(fin, "%d", &N);
    for (int i = 0; i < N; i++) {
        int r1, c1, r2, c2; fscanf(fin, "%d%d%d%d", &r1, &c1, &r2, &c2);
        r1--; c1--; r2--; c2--;
        setg(r1, c1, r2, c2, 1);
    }
}

int main() {
    setlinebuf(stdout);
    
    init();
    solve();
    
    return 0;
}