제출 #1177250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177250		vicvic	Cezar (COCI16_cezar)	C++20	20 / 100	0 ms	328 KiB

cezar

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
int n;
string v[105], final[105];
int order[105], viz[50], outdegree[50];
set <int> vec[50], ivec[50];
vector <int> rnk;
int main ()
{
    cin >> n;
    int mxlen=0;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
        mxlen=max (mxlen, (int)v[i].size());
    }
    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[i][ind]-'a'+1].insert (final[j][ind]-'a'+1);
                    ivec[final[j][ind]-'a'+1].insert (final[i][ind]-'a'+1);
                    outdegree[final[i][ind]-'a'+1]++;
                    break;
                }
            }
            if (!ok && final[j].size()<final[i].size())
            {
                cout << "NE";
                return 0;
            }
        }
    }
    queue <int> coada;
    for (int i=1;i<=26;i++)
    {
        if (outdegree[i]==0)
        {
            coada.push (i);
            viz[i]=1;
        }
    }
    while (!coada.empty())
    {
        int x=coada.front();
        rnk.push_back (x);
        coada.pop ();
        for (auto chestie : ivec[x])
        {
            outdegree[chestie]--;
            if (outdegree[chestie]==0 && !viz[chestie])
            {
                viz[chestie]=1;
                coada.push (chestie);
            }
        }
    }
    if (rnk.size()<26)
    {
        cout << "NE";
        return 0;
    }
    cout << "DA\n";
    string ans;
    ans.resize (26);
    int cnt=0;
    for (auto chestie : rnk)
    {
        ans[chestie-1]='a'+cnt;
        cnt++;
    }
    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