Submission #1177617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177617		vicvic	Cezar (COCI16_cezar)	C++20	20 / 100	663 ms	508 KiB

cezar

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <cstring>
using namespace std;
int n;
string v[105], final[105];
int order[105], viz[550], outdegree[550];
set <int> vec[560], ivec[506];
int rnk[105];
int looped=0;
void check (int nod)
{
    if (viz[nod])
    {
        looped=1;
        return;
    }
    viz[nod]=1;
    for (auto chestie : vec[nod])
    {
        check (chestie);
    }
    viz[nod]=0;
}
int cnt=0;
void dfs (int nod)
{
    viz[nod]=1;
    for (auto chestie : vec[nod])
    {
        if (viz[chestie])
            continue;
        dfs (chestie);
    }
    rnk[nod]=cnt++;
}
int main ()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin >> order[i];
    }
    for (int i=1;i<=n;i++)
    {
        final[order[i]]=v[i];
    }
    for (int i=1;i<n;i++)
    {
        for (int j=i+1;j<=i+1;j++)
        {
            bool ok=0;
            for (int ind=0;ind<min (final[i].size(), final[j].size());ind++)
            {
                if (final[i][ind]!=final[j][ind])
                {
                    ok=1;
                    vec[final[j][ind]-'a'].insert (final[i][ind]-'a');
                    break;
                }
            }
            if (!ok && final[j].size()<final[i].size())
            {
                cout << "NE";
                return 0;
            }
        }
    }
    for (int i=0;i<26;i++)
    {
        memset (viz, 0, sizeof(viz));
        check (i);
        if (looped)
        {
            cout << "NE";
            return 0;
        }
    }
    memset (viz, 0, sizeof(viz));
    for (int i=0;i<26;i++)
    {
        if (!viz[i])
            dfs (i);
    }
    cout << "DA\n";
    string ans;
    ans.resize (26);
    for (int i=0;i<26;i++)
    {
        ans[rnk[i]]=i+'a';
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10