Submission #743661

#	Time	Username	Problem	Language	Result	Execution time	Memory
743661		lukadupli	Dijamant (COI16_dijament)	C++14	100 / 100	382 ms	26428 KiB

dijament

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int n, cnt = 0, depth[MAXN];
map<string, int> mapa;
set<int> orgs[MAXN];

bool add(string& klasa, vector<string>& dads){
    if(mapa.find(klasa) != mapa.end()) return 0;

    vector<int> ds;
    for(string& d : dads){
        if(mapa.find(d) == mapa.end()) return 0;
        ds.push_back(mapa[d]);
    }

    sort(ds.begin(), ds.end(), [](int a, int b){return depth[a] > depth[b]; });

    set<int> s;
    int maxi = -1;
    for(int d : ds){
        if(s.find(d) != s.end()) continue;

        for(int e : orgs[d]){
            if(s.find(e) != s.end()) return 0;
            s.insert(e);
        }
        s.insert(d);

        maxi = max(maxi, depth[d]);
    }

    mapa[klasa] = ++cnt;
    orgs[cnt] = s;
    depth[cnt] = maxi + 1;

    return 1;
}

vector<string> dads;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        string k;
        cin >> k;

        char c;
        cin >> c;

        dads.clear();
        string in = "";
        while(in != ";"){
            cin >> in;
            dads.push_back(in);
        }
        dads.pop_back();

        if(add(k, dads)) cout << "ok\n";
        else cout << "greska\n";
    }

	return 0;
}

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