Guest User

Untitled

a guest
Jan 8th, 2015
272
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <stack>
  6. #define MAX 1000000000000000001LL
  7. #define pb push_back
  8. #define lli unsigned long long int
  9. #define WHITE 0
  10. #define GRAY 1
  11. #define BLACK 2
  12. using namespace std;
  13.  
  14. lli x[100005];
  15. lli y[100005];
  16. int change[100005];
  17. map <lli, int> mapa;
  18.  
  19. vector <int> g[8 * 100005];
  20.  
  21. int ncomp;
  22. int index;
  23. int idx[8 * 100005];
  24. int lowlink[8 * 100005];
  25. int comp[8 * 100005];
  26. int color[8 * 100005];
  27. int max_node_num[100005];
  28.  
  29. stack <int> pilha;
  30.  
  31. void strong_connect(int node) {
  32.     int viz;
  33.     int w;
  34.  
  35.     index++;
  36.     idx[node] = index;
  37.     lowlink[node] = index;
  38.     color[node] = GRAY;
  39.     pilha.push(node);
  40.  
  41.     for (int i = 0; i < (int)g[node].size(); i++) {
  42.         viz = g[node][i];
  43.  
  44.         if (color[viz] == WHITE) {
  45.             strong_connect(viz);
  46.             lowlink[node] = min(lowlink[node], lowlink[viz]);
  47.         } else if (color[viz] == GRAY) {
  48.             lowlink[node] = min(lowlink[node], idx[viz]);
  49.         }
  50.     }
  51.  
  52.     if (lowlink[node] == idx[node]) {
  53.         ncomp++;
  54.         do {
  55.             w = pilha.top();
  56.             pilha.pop();
  57.             color[w] = BLACK;
  58.             comp[w] = ncomp;
  59.         } while (w != node);
  60.     }
  61.     return;
  62. }
  63.  
  64. void add_edge(int a, int b) {
  65.     g[a].pb(b);
  66.     return;
  67. }
  68.  
  69. int main(void) {
  70.     int n;
  71.     int aux1, aux2;
  72.     int l, r, mid;
  73.     int impossible;
  74.     int node_num = 2;
  75.     int a, b;
  76.     int ok;
  77.  
  78.     scanf(" %d", &n);
  79.  
  80.     for (int i = 0; i < n; i++) {
  81.         scanf(" %lld %lld %d %d", &x[i], &y[i], &aux1, &aux2);
  82.         y[i] += MAX;
  83.         if (mapa[x[i]] == 0) {
  84.             mapa[x[i]] = node_num;
  85.             node_num += 2;
  86.         }
  87.         if (mapa[y[i]] == 0) {
  88.             mapa[y[i]] = node_num;
  89.             node_num += 2;
  90.         }
  91.         max_node_num[i] = node_num;
  92.         if (aux1 == aux2) {
  93.             change[i] = 0;
  94.         } else {
  95.             change[i] = 1;
  96.         }
  97.     }
  98.  
  99.     l = 0;
  100.     r = n - 1;
  101.     impossible = n;
  102.     while(l <= r) {
  103.         ok = 1;
  104.         mid = (l + r) / 2;
  105.  
  106.         //printf("mid = %d\n", mid);
  107.  
  108.         for (int i = 2; i < max_node_num[mid]; i++) {
  109.             g[i].clear();
  110.             color[i] = WHITE;
  111.         }
  112.         for (int i = 0; i <= mid; i++) {
  113.             a = mapa[x[i]];
  114.             b = mapa[y[i]];
  115.  
  116.             //printf("a = %d, b = %d\n", a, b);
  117.  
  118.             if (change[i]) {
  119.                 add_edge(a + 1, b);
  120.                 add_edge(b + 1, a);
  121.                 add_edge(a, b + 1);
  122.                 add_edge(b, a + 1);
  123.             } else {
  124.                 add_edge(a, b);
  125.                 add_edge(b, a);
  126.                 add_edge(a + 1, b + 1);
  127.                 add_edge(b + 1, a + 1);
  128.             }
  129.         }
  130.  
  131.         /*for (int i = 2; i < node_num; i++) {
  132.             printf("i = %d -- ", i);
  133.             for (int j = 0; j < (int)g[i].size(); j++) {
  134.                 printf("%d ", g[i][j]);
  135.             }
  136.             printf("\n");
  137.         } */
  138.  
  139.         index = 0;
  140.         ncomp = 0;
  141.         pilha = stack<int>();
  142.         for (int i = 2; i < max_node_num[mid]; i++) {
  143.             //printf("strong, i = %d, color[i] = %d\n", i, color[i]);
  144.             if (color[i] == WHITE) {
  145.                 strong_connect(i);
  146.             }
  147.         }
  148.  
  149.         for (int i = 2; i < max_node_num[mid]; i += 2) {
  150.             //printf("i = %d, comp[i] = %d, comp[i + 1] = %d\n", i, comp[i], comp[i + 1]);
  151.             if (comp[i] == comp[i + 1]) {
  152.                 ok = 0;
  153.                 break;
  154.             }
  155.         }
  156.  
  157.         //printf("ok = %d\n", ok);
  158.         if (ok) {
  159.             l = mid + 1;
  160.         } else {
  161.             impossible = mid;
  162.             r = mid - 1;
  163.         }
  164.     }
  165.  
  166.     for (int i = 0; i < impossible && i < n; i++) {
  167.         printf("Yes\n");
  168.     }
  169.     for (int i = impossible; i < n; i++) {
  170.         printf("No\n");
  171.     }
  172.  
  173.     return 0;
  174. }
RAW Paste Data