[Problem link](https://dmoj.ca/problem/coi15p1)↵
↵
I implemented a fairly straightforward soln for this problem that is very similar to the editorial in essense. It uses bitsets and the main logic goes as follows:↵
↵
As all ancestors for a node (lets say node a) are known when the node is first created, we can determine the nodes "b" for which a and b could form the middle part of a diamond. Whenever a new class is created, I first check if any pair of ancestors for the new class form such a couple (I denote below as "hate[][]"). If so this would create a diamond and we can terminate our search.↵
↵
Otherwise I will proceed to calculate new such pairs having the new node as "a". ↵
I believe the impl is not too incomprehensible but I will be happy to answer questions. This code gets 27 points so I dont believe anything is wrong with the parsing.↵
here is my submission code: ↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define ff first↵
#define ss second↵
#define all(x) x.begin(),x.end()↵
#define sp << " " << ↵
using namespace std;↵
↵
const int N =1e5+10,MOD = 1e9+7,inf = 2e9;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
int nd = 0;↵
bitset<1001> go[1001],come[1001],hate[1001],share;↵
string trash;↵
getline(cin,trash);↵
map<string,int> mp;↵
for (int i = 1;i<=n;i++) {↵
string name,realname;↵
getline(cin,name);↵
string cur;↵
int start = 0;↵
vi pars;↵
bool fl = 1;↵
for (int j = 0;j<name.size();j++) {↵
if (name[j] == ':') start = 1;↵
if (!start && name[j] >= 'a' && name[j] <= 'z') realname+=name[j];↵
if (start && name[j] >= 'a' && name[j] <= 'z') cur+=name[j];↵
else {↵
if (!cur.empty()) {↵
if (!mp.count(cur)) {↵
fl = 0;↵
break;↵
}↵
pars.push_back(mp[cur]);↵
}↵
cur.clear();↵
}↵
}↵
if (!fl || mp[realname]) {↵
cout << "greska" << endl;↵
continue;↵
}↵
++nd;↵
come[nd].set(nd);↵
go[nd].set(nd);↵
for (auto it : pars) come[nd]|=come[it];↵
for (int j = 1;j<nd && fl;j++) {↵
if (!come[nd][j]) continue;↵
for (int jj = j+1;jj<nd && fl;jj++) {↵
if (come[nd][jj] && hate[j][jj]) {↵
fl = 0;↵
break;↵
}↵
}↵
}↵
if (!fl) {↵
come[nd].reset();↵
go[nd].reset();↵
--nd;↵
cout << "greska" << endl;↵
continue; ↵
}↵
cout << "ok" << endl;↵
for (int j = 1;j<nd;j++) {↵
if (come[nd][j]) go[j][nd] = 1;↵
}↵
mp[realname] = nd;↵
//cout << realname << " IS " << nd << '\n';↵
share.reset();↵
for (int j = 1;j<nd;j++){↵
if (come[nd][j]) {↵
share|=go[j];↵
}↵
}↵
for (int j = 1;j<nd;j++) {↵
if (share[j] && !go[j][nd]) {↵
hate[nd][j] = hate[j][nd] = 1;↵
}↵
}↵
}↵
} ↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
#ifdef Dodi↵
freopen("in.txt","r",stdin);↵
freopen("out.txt","w",stdout);↵
#endif↵
int t = 1;↵
//cin >> t;↵
while (t --> 0) solve();↵
} ↵
~~~~~↵
↵
↵
I implemented a fairly straightforward soln for this problem that is very similar to the editorial in essense. It uses bitsets and the main logic goes as follows:↵
↵
As all ancestors for a node (lets say node a) are known when the node is first created, we can determine the nodes "b" for which a and b could form the middle part of a diamond. Whenever a new class is created, I first check if any pair of ancestors for the new class form such a couple (I denote below as "hate[][]"). If so this would create a diamond and we can terminate our search.↵
↵
Otherwise I will proceed to calculate new such pairs having the new node as "a". ↵
I believe the impl is not too incomprehensible but I will be happy to answer questions. This code gets 27 points so I dont believe anything is wrong with the parsing.↵
here is my submission code: ↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define ff first↵
#define ss second↵
#define all(x) x.begin(),x.end()↵
#define sp << " " << ↵
using namespace std;↵
↵
const int N =1e5+10,MOD = 1e9+7,inf = 2e9;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
int nd = 0;↵
bitset<1001> go[1001],come[1001],hate[1001],share;↵
string trash;↵
getline(cin,trash);↵
map<string,int> mp;↵
for (int i = 1;i<=n;i++) {↵
string name,realname;↵
getline(cin,name);↵
string cur;↵
int start = 0;↵
vi pars;↵
bool fl = 1;↵
for (int j = 0;j<name.size();j++) {↵
if (name[j] == ':') start = 1;↵
if (!start && name[j] >= 'a' && name[j] <= 'z') realname+=name[j];↵
if (start && name[j] >= 'a' && name[j] <= 'z') cur+=name[j];↵
else {↵
if (!cur.empty()) {↵
if (!mp.count(cur)) {↵
fl = 0;↵
break;↵
}↵
pars.push_back(mp[cur]);↵
}↵
cur.clear();↵
}↵
}↵
if (!fl || mp[realname]) {↵
cout << "greska" << endl;↵
continue;↵
}↵
++nd;↵
come[nd].set(nd);↵
go[nd].set(nd);↵
for (auto it : pars) come[nd]|=come[it];↵
for (int j = 1;j<nd && fl;j++) {↵
if (!come[nd][j]) continue;↵
for (int jj = j+1;jj<nd && fl;jj++) {↵
if (come[nd][jj] && hate[j][jj]) {↵
fl = 0;↵
break;↵
}↵
}↵
}↵
if (!fl) {↵
come[nd].reset();↵
go[nd].reset();↵
--nd;↵
cout << "greska" << endl;↵
continue; ↵
}↵
cout << "ok" << endl;↵
for (int j = 1;j<nd;j++) {↵
if (come[nd][j]) go[j][nd] = 1;↵
}↵
mp[realname] = nd;↵
//cout << realname << " IS " << nd << '\n';↵
share.reset();↵
for (int j = 1;j<nd;j++){↵
if (come[nd][j]) {↵
share|=go[j];↵
}↵
}↵
for (int j = 1;j<nd;j++) {↵
if (share[j] && !go[j][nd]) {↵
hate[nd][j] = hate[j][nd] = 1;↵
}↵
}↵
}↵
} ↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
#ifdef Dodi↵
freopen("in.txt","r",stdin);↵
freopen("out.txt","w",stdout);↵
#endif↵
int t = 1;↵
//cin >> t;↵
while (t --> 0) solve();↵
} ↵
~~~~~↵
↵
