Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class IpTree{
  6. public:
  7.     IpTree* child0 = NULL;
  8.     IpTree* child1 = NULL;
  9.     bool isEnd = false;
  10. };
  11.  
  12. int main()
  13. {
  14.     int T;
  15.     scanf("%d", &T);
  16.     while (T--) {
  17.         printf("T = %d", T);
  18.         IpTree* root = new IpTree();
  19.         int M, N;
  20.         scanf("%d %d", &M, &N);
  21.         while (M--) {
  22.             int a, b, c, d, bits;
  23.             IpTree* p = root;
  24.             scanf("%d.%d.%d.%d/%d", &a, &b, &c, &d, &bits);
  25.             unsigned int temp = (a << 24) | (b << 16) | (c << 8) | d;
  26.             //printf("a, b, c, d, bits, temp === %X, %X, %X, %X, %X, %X\n", a, b, c, d, bits, temp);
  27.             unsigned int nowBit = (1 << 31);
  28.             while (bits--) {
  29.                 //printf("nowBit, temp, & === %X %X %X\n", nowBit, temp, nowBit & temp);
  30.                 if ((nowBit & temp) != 0) {
  31.                     if (p->child1 == NULL) {
  32.                         p->child1 = new IpTree();
  33.                     }
  34.                     p = p->child1;
  35.                 }
  36.                 else {
  37.                     if (p->child0 == NULL) {
  38.                         p->child0 = new IpTree();
  39.                     }
  40.                     p = p->child0;
  41.                 }
  42.                 nowBit >>= 1;
  43.             }
  44.             p->isEnd = true;
  45.         }
  46.         while (N--) {
  47.             int a, b, c, d;
  48.             IpTree* p = root;
  49.             scanf("%d.%d.%d.%d", &a, &b, &c, &d);
  50.             unsigned int temp = (a << 24) | (b << 16) | (c << 8) | d;
  51.             //printf("a, b, c, d, temp === %X, %X, %X, %X, %X\n", a, b, c, d, temp);
  52.             bool isAccept = false;
  53.             for (unsigned int nowBit = (1 << 31); nowBit != 0; nowBit >>= 1) {
  54.                 //printf("nowBit, temp, & === %X %X %X\n", nowBit, temp, nowBit & temp);
  55.                 if (p->isEnd == true) {
  56.                     isAccept = true;
  57.                     printf("TRUE\n");
  58.                     break;
  59.                 }
  60.                 if ((nowBit & temp) != 0) {
  61.                     if (p->child1 == NULL) {
  62.                         isAccept = false;
  63.                         printf("FALSE\n");
  64.                         break;
  65.                     }
  66.                     p = p->child1;
  67.                 }
  68.                 else {
  69.                     if (p->child0 == NULL) {
  70.                         isAccept = false;
  71.                         printf("FALSE\n");
  72.                         break;
  73.                     }
  74.                     p = p->child0;
  75.                 }
  76.             }
  77.             //printf("%d\n", isAccept);
  78.         }
  79.     }
  80.    
  81.    return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement