SHARE
TWEET

Untitled

a guest Sep 25th, 2016 111 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:64000000")
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <list>
  7. #include <iterator>
  8. #include <cassert>
  9. #include <set>
  10. #include <queue>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <stack>
  14. #include <deque>
  15. #include <cmath>
  16. #include <memory.h>
  17. #include <cstdlib>
  18. #include <cstdio>
  19. #include <cctype>
  20. #include <algorithm>
  21. #include <utility>
  22. #include <time.h>
  23. #include <complex>
  24. using namespace std;
  25.  
  26. #define FOR(i, a, b) for(int i=(a);i<(b);i++)
  27. #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
  28. #define FILL(A,value) memset(A,value,sizeof(A))
  29.  
  30. #define ALL(V) V.begin(), V.end()
  31. #define SZ(V) (int)V.size()
  32. #define PB push_back
  33. #define MP make_pair
  34. #define Pi 3.14159265358979
  35. #define x0 ikjnrmthklmnt
  36. #define y0 lkrjhkltr
  37. #define y1 ewrgrg
  38.  
  39. typedef long long Int;
  40. typedef unsigned long long UInt;
  41. typedef vector<int> VI;
  42. typedef pair<int, int> PII;
  43. typedef pair<Int, Int> PLL;
  44. typedef pair<double, double> PDD;
  45. typedef complex<double> base;
  46.  
  47. const int INF = 1000000000;
  48. const int BASE = 1000000007;
  49. const int MAX = 200007;
  50. const int MAXV = 100007;
  51. const int MAXE = 100000;
  52. const int ADD = 1000000;
  53. const int MOD = 1000000007;
  54. const int CNT = 800;
  55.  
  56. vector<PII> X[MAX];
  57. vector<PII> Y[MAX];
  58.  
  59. VI G[MAX];
  60.  
  61. bool U[MAX];
  62.  
  63. int sum;
  64.  
  65. int d[MAX];
  66.  
  67. bool R[MAX];
  68. int tin[MAX];
  69. int fup[MAX];
  70. int timer = 0;
  71.  
  72. int n;
  73. int UU[MAX];
  74.  
  75. int dfs2(int v)
  76. {
  77.     UU[v] = 1;
  78.     int ret = 1;
  79.     FOR(i,0,SZ(G[v]))
  80.     {
  81.         int to = G[v][i];
  82.         if (UU[to]) continue;
  83.         ret += dfs2(to);
  84.     }
  85.     return ret;
  86. }
  87.  
  88. int comp;
  89.  
  90. void dfs(int v , int p)
  91. {
  92.     tin[v] = timer ++;
  93.  
  94.     U[v] = 1;
  95.     fup[v] = tin[v];
  96.     d[v] = 1;
  97.  
  98.     int dup = 0;
  99.  
  100.     FOR(i,0,SZ(G[v]))
  101.     {
  102.         int to = G[v][i];
  103.         if (to == p) continue;
  104.         if (U[to])
  105.         {
  106.             fup[v] = min(fup[v] , tin[to]);
  107.         }
  108.         else
  109.         {
  110.             dfs(to, v);
  111.             d[v] += d[to];
  112.             fup[v] = min(fup[v] , fup[to]);
  113.  
  114.             if (fup[to] >= tin[v])
  115.             {
  116.                 if (d[to] % 2 == 1) R[v] = 0;
  117.             }
  118.             else
  119.             {
  120.                 dup += d[to];
  121.             }
  122.         }
  123.     }
  124.  
  125.     dup += comp - d[v];
  126.     if (dup % 2 == 1) R[v] = 0;
  127.  
  128. }
  129.  
  130. int main()
  131. {
  132.     //freopen("in.txt", "r", stdin);
  133.     //freopen("distance.in",  "r", stdin);
  134.     //freopen("distance.out", "w", stdout);
  135.     //freopen("out.txt" , "w" , stdout);
  136.  
  137.  
  138.     cin >> n;
  139.     vector<PII> A;
  140.     FOR(i,0,2 * n + 1)
  141.     {
  142.         int x , y;
  143.         scanf("%d%d" , &x , &y);
  144.  
  145.         X[x].push_back(MP(y , i));
  146.         Y[y].push_back(MP(x , i));
  147.     }
  148.  
  149.     FOR(i,0,MAX)
  150.     {
  151.         sort(ALL(X[i]));
  152.         FOR(j,0,SZ(X[i]) - 1)
  153.         {
  154.             G[X[i][j].second].push_back(X[i][j + 1].second);
  155.             G[X[i][j + 1].second].push_back(X[i][j].second);
  156.         }
  157.         FOR(j,0,SZ(X[i]) - 2)
  158.         {
  159.             G[X[i][j + 2].second].push_back(X[i][j].second);
  160.             G[X[i][j].second].push_back(X[i][j + 2].second);
  161.         }
  162.     }
  163.     FOR(i,0,MAX)
  164.     {
  165.         sort(ALL(Y[i]));
  166.         FOR(j,0,SZ(Y[i]) - 1)
  167.         {
  168.             G[Y[i][j + 1].second].push_back(Y[i][j].second);
  169.             G[Y[i][j].second].push_back(Y[i][j + 1].second);
  170.         }
  171.         FOR(j,0,SZ(Y[i]) - 2)
  172.         {
  173.             G[Y[i][j + 2].second].push_back(Y[i][j].second);
  174.             G[Y[i][j].second].push_back(Y[i][j + 2].second);
  175.         }
  176.     }
  177.  
  178.     FOR(i,0,2 * n + 1)
  179.     {
  180.         R[i] = 1;
  181.     }
  182.     int cnt = 0;
  183.     FOR(i,0,2 * n + 1)
  184.     {
  185.         if (U[i]) continue;
  186.         comp = dfs2(i);
  187.         dfs(i , -1);
  188.         if (comp % 2 == 1) ++ cnt;
  189.     }
  190.  
  191.     if (cnt > 1)
  192.     {
  193.         FOR(i,0,2 * n + 1)
  194.             R[i] = 0;
  195.     }
  196.  
  197.     FOR(i,0,2 * n + 1)
  198.     {
  199.         if (R[i]) printf("OK\n");
  200.         else printf("NG\n");
  201.     }
  202.  
  203.     return 0;
  204. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top