This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<sstream>
using namespace std;
struct node {
int id;
vector<int> child;
vector<int> par;
set<int> allc;
node (int _id) {
id = _id;
}
};
int n;
map<string, int> objmap;
vector<node> objs;
vector<int> roots;
int vis[1002];
bool isChild(string a, string b) {
int ai = objmap[a], bi = objmap[b];
return objs[ai].allc.find(bi) != objs[ai].allc.end();
}
int dfs(int x, set<int>* sc) {
vis[x] = true;
if (sc->find(x) != sc->end()) return 1;
int ans = 0;
for (int v : objs[x].child) {
if (!vis[v]) {
ans += dfs(v, sc);
}
}
return ans;
}
void dfs2(int x, int o) {
objs[x].allc.insert(o);
for (int v : objs[x].par) {
dfs2(v, o);
}
}
int main() {
string nline; getline(cin, nline);
stringstream nstream(nline);
nstream >> n;
int ind = 0;
for (int i = 0; i < n; i++) {
//cout << "next obj" << endl;
string line; getline(cin, line);
stringstream ss(line);
string name; ss >> name;
//cout << "name: " << name << " yeah" << endl;
char c; ss >> c;
vector<string> pars;
string inh; ss >> inh;
while (inh != ";") {
pars.push_back(inh);
ss >> inh;
}
if (objmap.find(name) != objmap.end()) {
cout << "greska\n";
continue;
}
if (pars.empty()) {
objmap[name] = ind;
objs.push_back(node(ind));
roots.push_back(ind);
ind++;
cout << "ok\n";
continue;
}
bool flag = false;
for (string s : pars) {
if (objmap.find(s) == objmap.end()) {
cout << "greska\n";
flag = true;
break;
}
}
if (flag) continue;
//cout << "test" << endl;
bool ignore[1002];
memset(ignore, 0, sizeof(ignore));
vector<int> parInd;
set<int> parSet;
for (int pa = 0; pa < pars.size(); pa++) {
if (ignore[pa]) continue;
for (int pb = pa+1; pb < pars.size(); pb++) {
if (ignore[pb]) continue;
if (isChild(pars[pb], pars[pa])) {
ignore[pb] = true;
} else if (isChild(pars[pa], pars[pb])) {
ignore[pa] = true;
break;
}
}
if (ignore[pa]) continue;
parInd.push_back(objmap[pars[pa]]);
parSet.insert(objmap[pars[pa]]);
}
//cout << "removed dupes" << endl;
//for (int v : parInd) cout << v << " ";
//cout << endl;
flag = false;
for (int rt : roots) {
memset(vis, 0, sizeof(vis));
if (dfs(rt, &parSet) > 1) {
flag = true;
cout << "greska\n";
break;
}
}
if (flag) continue;
node curNode(ind);
for (int cpar : parInd) {
dfs2(cpar, ind);
objs[cpar].child.push_back(ind);
}
curNode.par = parInd;
objs.push_back(curNode);
objmap[name] = ind;
ind++;
cout << "ok\n";
}
}
Compilation message (stderr)
dijament.cpp: In function 'int main()':
dijament.cpp:97:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int pa = 0; pa < pars.size(); pa++) {
| ~~~^~~~~~~~~~~~~
dijament.cpp:99:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int pb = pa+1; pb < pars.size(); pb++) {
| ~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |