oj.uz

Submission #315790

# Submission time Handle Problem Language Result Execution time Memory
315790 2020-10-24T01:38:57 Z Vince729 Dijamant (COI16_dijament) C++11
100 / 100
 1516 ms 28264 KB 
#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

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++) {
      |                                 ~~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 1 ms 372 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 1 ms 372 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 400 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 25080 KB Output is correct
2 Correct 1516 ms 28264 KB Output is correct
3 Correct 264 ms 4728 KB Output is correct
4 Correct 18 ms 512 KB Output is correct
5 Correct 30 ms 896 KB Output is correct
6 Correct 65 ms 760 KB Output is correct
7 Correct 288 ms 900 KB Output is correct
8 Correct 1202 ms 1144 KB Output is correct
9 Correct 1071 ms 956 KB Output is correct
10 Correct 33 ms 640 KB Output is correct
11 Correct 23 ms 640 KB Output is correct
12 Correct 1140 ms 23136 KB Output is correct