Submission #1266221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266221		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<vector<int>> adj(26);
    function<void(int, int, int)> solve = [&](int l, int r, int p) {
        if (l >= r) return;
        string s = "";
        for (int i = l; i <= r; i++) {
            if (p >= a[i].size()) {
                s += ' ';
            }
            else {
                s += a[i][p];
            }
        }
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == ' ' && s[i - 1] != ' ') {
                cout << "NE\n";
                exit(0);
            }
            if (s[i] != s[i - 1] && s[i - 1] != ' ') {
                adj[s[i - 1] - 'a'].push_back(s[i] - 'a');
            }
        }
        while (l <= r && p >= a[l].size()) l++;
        int k = l;
        for (int i = l + 1; i <= r; i++) {
            if (a[i][p] != a[i - 1][p]) {
                solve(k, i - 1, p + 1);
                k = i;
            }
        }
        solve(k, r, p + 1);
    };
    solve(0, n - 1, 0);
    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