Submission #81492

#	Time	Username	Problem	Language	Result	Execution time	Memory
81492		ngot23	Cezar (COCI16_cezar)	C++11	0 / 100	2 ms	1016 KiB

cezar

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=30;
vector <int > g[N];
string s1[105], s2[105];
int n, visit[N], in[N], cur, c[N];

bool DFS(int u) {
    visit[u]=1;
    for(int v:g[u]) {
        if(visit[v]==0) {
            bool fl=DFS(v);
            if(!fl) return false;
        } else if(visit[v]==1) return false;
    }
    visit[u]=2;
    return true;
}

void DFS2(int u) {
    c[u]=cur++;
    for(int v:g[u]) {
        DFS2(v);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n;
    rep(i, 1, n) cin >> s1[i];
    rep(i, 1, n) {
        int u; cin >> u;
        s2[i]=s1[u];
    }
    int leng=s1[1].size();
    for(int i=1 ; i<n ; ++i) {
        rep(j, 0, leng-1) {
            if(s2[i][j]!=s2[i+1][j]) {
                int u=s2[i][j]-'a';
                int v=s2[i+1][j]-'a';
                g[u].push_back(v);
                ++in[v];
                break;
            }
        }
    }
    rep(i, 0, 25) {
        if(g[i].size()==0||visit[i]) continue;
        if(DFS(i)==false) return cout << "NE", 0;
    }
    rep(i, 0, 25) {
        if(!in[i]) DFS2(i);
    }
    cout << "DA\n";
    rep(i, 0, 25) {
        cout << (char)(c[i]+'a');
    }
    return 0;
}

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