Skip to content

Instantly share code, notes, and snippets.

@boompig boompig/icpc-klingons.cpp
Last active Aug 29, 2015

Embed
What would you like to do?
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int MAX_M = 10000;
const int MAX_N = 10000;
struct node {
int sup;
char f;
int i;
node *parent;
vector<node *> children;
int num_subordinates = 0;
node () {}
node (char fs, int s, int idx) {
f = fs;
sup = s;
i = idx;
}
ll hash() {
return ((ll) children.size() * 52 * MAX_M) + ((ll) num_subordinates * 26) + f - 66;
}
};
typedef vector<node *> vn;
typedef vector<bool> vb;
void count_subordinates(node* root) {
int s = 0;
for(int i = 0; i < root->children.size(); i++) {
count_subordinates(root->children[i]);
s += root->children[i]->num_subordinates + 1;
}
root->num_subordinates = s;
}
int best = 0;
void match_tree (node* root, vector<vb> &matches, map<ll, vn> &nmap) {
for(int i = 0; i < root->children.size(); i++) {
match_tree(root->children[i], matches, nmap);
}
ll h = root->hash();
int root_idx = root->i;
// definitely no match for me
if (nmap.find(h) == nmap.end()) return;
bool good;
for (int i = 0; i < nmap[h].size(); i++) {
int n_idx = nmap[h][i]->i;
good = true;
for (int c = 0; c < root->children.size(); c++) {
int c_idx = root->children[c]->i;
int nc_idx = nmap[h][i]->children[c]->i;
if (! matches[c_idx][nc_idx]) {
good = false;
break;
}
}
if (good) {
matches[root_idx][n_idx] = true;
if (root->num_subordinates + 1 > best) {
best = root->num_subordinates + 1;
}
}
}
}
int main () {
int t;
cin >> t;
for(; t > 0; t--) {
int M, N;
cin >> M >> N;
vector<node> m_soldiers;
vector<node> n_soldiers;
for (int i = 0; i < M; i++) {
char f;
int s;
cin >> f >> s;
m_soldiers.push_back(node(f, s, i));
}
for (int i = 0; i < N; i++) {
char f;
int s;
cin >> f >> s;
n_soldiers.push_back(node(f, s, i));
}
// link the btrees
for (int i = 0; i < M; i++) {
if (m_soldiers[i].sup >= 0) {
node *parent = &m_soldiers[m_soldiers[i].sup];
m_soldiers[i].parent = parent;
parent->children.push_back(&m_soldiers[i]);
}
}
for (int i = 0; i < N; i++) {
if (n_soldiers[i].sup >= 0) {
node *parent = &n_soldiers[n_soldiers[i].sup];
n_soldiers[i].parent = parent;
parent->children.push_back(&n_soldiers[i]);
}
}
node* m_root = &m_soldiers[0];
node* n_root = &n_soldiers[0];
// count the number of subordinates of each
count_subordinates(m_root);
count_subordinates(n_root);
// hash n_tree
map<ll, vn> nmap;
for (int i = 0; i < N; i++) {
node* n = &n_soldiers[i];
ll h = n->hash();
if (nmap.find(h) == nmap.end()) {
vector <node *> v;
nmap[h] = v;
nmap[h].push_back (n);
} else {
nmap[h].push_back(n);
}
}
// initialize matches
vector<vb> matches(M, vector<bool> (N, false));
best = 0;
match_tree(m_root, matches, nmap);
cout << best << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.