Problem

Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called Good Firewall (a.k.a., GFW). Network flows enter in the GFW will be forwarded or dropped according to pre-established forwarding policies.

Basically, a forwarding policy P is a list of IP subnets, {ip_subnet_1, …, ip_subnet_n}. If P is enabled in GFW, a network flow F with source and destination IP address both located in P can be accepted and forwarded by GFW, otherwise F will be dropped by GFW.

How will you design the GFW, if you take charge of the plan?

The input file contains no more than 32768 lines. Each line is in one of the following three formats:

E id n ip_subnet_1 ip_subnet_2 … ip_subnet_n
D id
F ip_src ip_dst

The first line means that a network policy P id (1<=id<=1024) is enabled in GFW, and there are n (1<=n <=15) IP subnets in P id. The second line means that policy P id (which is already enabled at least once) is disabled in GFW. The last line means that a network flow with source and destination IP address is entered in GFW, and you need to figure out whether GFW is going to forward (F) or drop (D) this flow:

1. If the source and destination IP address both are located in one of enabled policy group P id, GFW will forward this flow.

2. Otherwise GFW will drop this flow. That is, if the source or destination IP address is not located in any of enabled policy group, or they are only located in different enabled policy group(s), GFW will drop it.

IP subnets can be overlapped. An IP address may or may not be located in any policy group, and can also be located in multiple policy groups.

In the global routing table, most of the IP subnets have at least 2^8 IP addresses, and at most 2^24 IP addresses. In our dataset, every IP subnet has a prefix length between 8 and 24.

For each ‘F’ operation, output a single ‘F’ (forward) or ‘D’ (drop) in a single line. Just see the sample output for more detail.

Code

#include <bits/stdc++.h>
using namespace std;

char op;
int a, ip, id, n, port;
bool cancle;

struct Trie {
static const int maxnode = 400000, sigma_size = 2;
int ch[maxnode][sigma_size], sz;
set<int> st[maxnode];

Trie() { clear(); }
void clear() { sz = 1; memset(ch, 0, sizeof(ch)); st.clear(); }

void insert(const int *ip, int pid, int len) {
int u = 0;
for(int i = 0; i < len; ++i) {
int id = ip[i];
if(!ch[u][id]) {
memset(ch[sz], 0, sizeof(ch[sz]));
st[sz].clear();
ch[u][id] = sz++;
}
u = ch[u][id];
}
st[u].insert(pid);
}

void query(const int *ip, set<int> &ans) {
int u = 0;
for(int i = 0; i < 32; ++i) {
int id = ip[i];
if(!ch[u][id]) return;
else {
u = ch[u][id];
for(auto j : st[u])
if(!cancle[j])
ans.insert(j);
}
}
}
}trie;

void encode(int a) {
for(int i = 0; i < 4; ++i)
for(int j = ((i + 1) * 8) - 1; j >= i * 8; --j) {
ip[j] = a[i] % 2;
a[i] /= 2;
}
}

int main() {
trie.clear();
while(~scanf("%s", op)) {
if(op == 'E') {
scanf("%d%d", &id, &n);
for(int i = 0; i < n; ++i) {
scanf("%d.%d.%d.%d/%d", &a, &a, &a, &a, &port);
encode(a);
trie.insert(ip, id, port);
}
cancle[id] = false;
}
else if(op == 'D') {
scanf("%d", &id);
cancle[id] = true;
}
else if(op == 'F') {
set<int> st;
for(int i = 0; i < 2; ++i) {
scanf("%d.%d.%d.%d", &a, &a, &a, &a);
encode(a);
trie.query(ip, st[i]);
}
vector<int> ans;
set_intersection(st.begin(), st.end(), st.begin(), st.end(), back_inserter(ans));
puts(ans.empty() ? "D" : "F");
}
}
return 0;
}