Submission #52313

#	Time	Username	Problem	Language	Result	Execution time	Memory
52313		Milki	Dijamant (COI16_dijament)	C++14	100 / 100	339 ms	16372 KiB

dijament

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = 0; i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e3 + 5;

int n;
map<string, int> id;
vector <int> parents[MAXN];
bool bio[MAXN];
int curr;

bool check(string &name, vector <string> &par){
    if(id[name] != 0) return false;
    for(auto it : par){
        if(id[it] == 0)
            return false;
    }
    vector <int> parId;
    REP(i, (int)par.size()){
        parId.push_back(id[par[i]]);
    }
    sort(parId.rbegin(), parId.rend());

    memset(bio, 0, curr + 1);
    for(auto it : parId){
        if(bio[it]) continue;

        for(auto p : parents[it]){
            if(bio[p]) return false;
            bio[p] = 1;
        }
    }

    id[name] = ++curr;
    for(auto it : parId)
        bio[it] = 1;

    FOR(i, 1, curr)
        if(bio[i])
            parents[curr].push_back(i);
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    REP(i, n){
        string name, tmp;
        vector<string> v;
        cin >> name >> tmp;
        cin >> tmp;
        while(tmp != ";"){
            v.push_back(tmp);
            cin >> tmp;
        }

        if(check(name, v))
            cout << "ok\n";
        else
            cout << "greska\n";
    }
}

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