20200722T2 【NOIP2015模拟10.29A组】网格图游戏

Description

Input

Output

Sample Input

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

Sample Output

YES
YES
NO
NO

Data Constraint

solution

因为处理转换点的问题找了一晚上bug

先埋坑

气死了。。。。

——————————————————————————————

对于一个平面图，任何一条边两侧都是两个平面区域，在纸上画图发现，如果是两个区域，断开这条边我们还可以从外面绕过去得到路径，如果已经合并成一个区域了，就找不到路径。

所以可以用并查集维护。

对于本题来说，画出网格图，中间的是白块，容易发现如果两个点在删掉这条边以前就联通，肯定有白色区域包围一个点，它出不去，就无法链接到另一个点，于是就把删边转化为加边询问连通性，用并查集很好维护。

对于四边的点，我们可以在最外层套一层白块，然后预处理最外面的白块都连通即可。

时间复杂度：

code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<queue>
  7 #include<vector>
  8 #include<stack>
  9 #include<set>
 10 #include<deque>
 11 #include<map>
 12 using namespace std;
 13 
 14 template <typename T> void read(T &x) {
 15     x = 0; int f = 1; char c;
 16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
 17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
 18     x *= f;
 19 }
 20 template <typename T> void write(T x){
 21     if (x < 0) putchar('-'), x = -x;
 22     if (x > 9) write(x / 10);
 23     putchar(x % 10 + '0');
 24 }
 25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
 26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
 27 
 28 #define ll long long
 29 #define inf 1234567890
 30 #define next net
 31 #define P 1000000007
 32 #define N 500020
 33 #define mid ((l+r)>>1)
 34 #define lson (o<<1)
 35 #define rson (o<<1|1)
 36 #define R register
 37 
 38 int n, k, last = 1, maxn;
 39 int aa, bb, dd, ee;
 40 char cc, ff;
 41 int f[800000];
 42 int getf(int x)
 43 {
 44     return f[x] == x ? x : f[x] = getf(f[x]);
 45 }
 46 void bing(int x,int y)
 47 {
 48     f[getf(y)] = f[getf(x)];
 49 }
 50 void solve(int x,int y)
 51 {
 52     if(getf(x) == getf(y))
 53     {
 54         printf("NO
");
 55         last = 0;
 56         return;
 57     }
 58     bing(x, y);
 59     printf("YES
");
 60     last = 1;
 61     return;
 62 }
 63 signed main()
 64 {
 65     read(n); read(k);
 66     maxn = (n + 1) * (n + 1);
 67     for(R int i = 1; i <= maxn; i++) f[i] = i;
 68     for(R int i = 1; i <= n; i++) bing(i, i + 1);
 69     for(R int i = 0; i <= n - 1; i++) bing(i * (n + 1) + 1, (i + 1) * (n + 1) + 1);
 70     for(R int i = 0; i <= n - 1; i++) bing(i * (n + 1) + n + 1, (i + 1) * (n + 1) + n + 1);
 71     for(R int i = 1; i <= n; i++) bing(n * (n + 1) + i, n * (n + 1) + i + 1);
 72     while(k--)
 73     {
 74         read(aa); read(bb); cc = getchar(); while(cc != 'E' && cc != 'N') cc = getchar();
 75         read(dd); read(ee); ff = getchar(); while(ff != 'E' && ff != 'N') ff = getchar();
 76         aa = (aa - 1) * n + bb;
 77         dd = (dd - 1) * n + ee;
 78         if(last)
 79         {
 80             //writeln(aa);
 81             if(cc == 'E')
 82             {
 83                 //writeln(aa / n);
 84                 aa = ((aa % n == 0) ? (aa / n) : (aa / n + 1)) * (n + 1) + (aa % n) + (aa % n == 0) * n;
 85                 bb = aa + 1;//writesn(aa); writeln(bb);
 86                 solve(aa, bb); 
 87             }
 88             else
 89             {
 90                 aa = (aa / n) * (n + 1) + (aa % n + 1);
 91                 bb = aa + n + 1;//writesn(aa); writeln(bb);
 92                 solve(aa, bb);
 93             }
 94         }
 95         else
 96         {
 97             //writeln(dd);
 98             if(ff == 'E')
 99             {
100                 dd = ((dd % n == 0) ? (dd / n) : (dd / n + 1)) * (n + 1) + (dd % n) + (dd % n == 0) * n;
101                 ee = dd + 1;//writesn(dd); writeln(ee);
102                 solve(dd, ee); 
103             }
104             else
105             {
106                 dd = (dd / n) * (n + 1) + (dd % n + 1);
107                 ee = dd + n + 1;//writesn(dd); writeln(ee);
108                 solve(dd, ee);
109             }
110         }
111     }
112     return 0;
113 }