## Connect [Richard Peng, 2007]

ქართული თარგმანი არ არის დამატებული

## 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; int block[Blockn]; int changed[Blockn]; inline void setg(int r1, int c1, int r2, int c2, int x) { if (c1 == c2) G[c1] = 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] && (m1 || m2)) m1 = m2 = 1; if (!G[i]) m1 = 0; if (!G[i]) 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] = m1; block[x][t] = 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]) newm1 = 1; if (m1 && block[i]) newm2 = 1; if (m2 && block[i]) newm1 = 1; if (m2 && block[i]) newm2 = 1; m1 = newm1; m2 = newm2; if (!m1 && !m2) return false; } process(b2 * Blocksize, c2, m1, m2); } if (G[c2] && (m1 || m2)) m1 = m2 = 1; if ((r2 == 0 && m1) || (r2 == 1 && m2)) return true; else return false; } char line; inline void solve() { while (1) { fgets(line, 100, stdin); if (line == '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;
int block[Blockn];
int changed[Blockn];

inline void setg(int r1, int c1, int r2, int c2, int x) {
if (c1 == c2) G[c1] = 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] && (m1 || m2)) m1 = m2 = 1;
if (!G[i]) m1 = 0;
if (!G[i]) 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] = m1;
block[x][t] = 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]) newm1 = 1;
if (m1 && block[i]) newm2 = 1;
if (m2 && block[i]) newm1 = 1;
if (m2 && block[i]) newm2 = 1;

m1 = newm1; m2 = newm2;
if (!m1 && !m2) return false;
}

process(b2 * Blocksize, c2, m1, m2);
}

if (G[c2] && (m1 || m2)) m1 = m2 = 1;

if ((r2 == 0 && m1) || (r2 == 1 && m2)) return true;
else return false;
}

char line;
inline void solve() {
while (1) {
fgets(line, 100, stdin);
if (line == '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;
}
```