Submission #1266223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266223		canhnam357	Cezar (COCI16_cezar)	C++20	70 / 100	1 ms	328 KiB

cezar

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<string> b(n);
    for (string &s : b) cin >> s;
    vector<string> a;
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        a.push_back(b[--p]);
    }
    vector<int> adj[26];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i].find(a[j]) == 0) {
                cout << "NE\n";
                return 0;
            }
            if (a[j].find(a[i]) == 0) continue;
            for (int k = 0;; k++) {
                if (a[i][k] != a[j][k]) {
                    adj[a[i][k] - 'a'].push_back(a[j][k] - 'a');
                    break;
                }
            }
        }
    }
    vector<int> topo, vis(26);
    function<void(int)> dfs =  [&](int u) {
        vis[u] = 1;
        for (int v : adj[u]) {
            if (!vis[v]) dfs(v);
            else if (vis[v] == 1) {
                cout << "NE\n";
                exit(0);
            }
        }
        topo.push_back(u);
        vis[u] = 2;
    };
    for (int i = 0; i < 26; i++) {
      sort(adj[i].begin(), adj[i].end());
      adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    for (int i = 0; i < 26; i++) {
        if (!vis[i] && adj[i].size()) dfs(i);
    }
    reverse(topo.begin(), topo.end());
    cout << "DA\n";
    string ans(26, ' ');
    for (int i = 0; i < topo.size(); i++) {
        ans[topo[i]] = i + 'a';
    }
    for (char c = topo.size() + 'a'; c <= 'z'; c++) {
        for (char &ch : ans) {
            if (ch == ' ') {
                ch = c;
                break;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

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