Submission #1344917

#TimeUsernameProblemLanguageResultExecution timeMemory
1344917gkos5678Dijamant (COI16_dijament)C++20
13 / 100
2096 ms19508 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef vector<int> vi;
typedef vector<string> vs;

const int maxn = 1005;

int n, tr, d[maxn];
bool def[maxn * maxn], vis[maxn], vis1[maxn];
vi ns[maxn], ou[maxn], in[maxn];
string sd[maxn];
vs nss[maxn];
map<string, int> m;
bitset<maxn> b[maxn], ukor, ann;

void dfs1(int v){
    vis[v] = 1;
    for (int ss : in[v])
        dfs1(ss);
}

void dfs2(int v){
    if (vis1[v]) return;
    vis1[v] = 1;
    for (int ss : ou[v])
        dfs2(ss);
}

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

    cin >> n;
    tr = 1;
    for (int i = 1; i <= n; i++){
        cin >> sd[i];
        string dv, p;
        cin >> dv;
        while(true){
            cin >> p;
            if (p == ";") break;
            nss[i].pb(p);
        }
    }
    for (int i = 1; i <= n; i++){
        if (m[sd[i]] == 0){
            m[sd[i]] = tr;
            tr++;
        }
    }
    for (int i = 1; i <= n; i++){
        for (string el : nss[i]){
            if (m[el] == 0){
                m[el] = tr;
                tr++;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        d[i] = m[sd[i]];
        for (string s : nss[i])
            ns[i].pb(m[s]);
    }

    for (int i = 1; i <= n; i++){
        bool ok = !def[d[i]];
        for (int el : ns[i])
            ok &= def[el];
        if (!ok){
            cout << "greska\n";
            continue;
        }
        ukor = 0;
        ann = 0;
        for (int el : ns[i]){
            ann[el] = 1;
            ukor |= b[el];
        }
        ukor &= ann;
        if (ukor != 0){
            cout << "greska\n";
            continue;
        }
        for (int el : ns[i]){
            ou[el].pb(d[i]);
            in[d[i]].pb(el);
        }
        for (int j = 1; j <= n; j++)
            vis[j] = vis1[j] = 0;
        dfs1(d[i]);
        for (int j = 1; j <= n; j++)
            if (vis[j])
                dfs2(j);
        def[d[i]] = 1;
        cout << "ok\n";
        for (int j = 1; j <= n; j++)
            b[d[i]][j] = b[j][d[i]] = (!vis[j] && vis1[j]);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...