제출 #315790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315790		Vince729	Dijamant (COI16_dijament)	C++11	100 / 100	1516 ms	28264 KiB

dijament

#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";
    }
}

컴파일 시 표준 에러 (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++) {
      |                                 ~~~^~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44