Submission #315790

#TimeUsernameProblemLanguageResultExecution timeMemory
315790Vince729Dijamant (COI16_dijament)C++11
100 / 100
1516 ms28264 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...