Submission #1220197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220197		sunflower	Cezar (COCI16_cezar)	C++17	10 / 100	1 ms	328 KiB

cezar

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define F first
#define S second
#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

#define MAX_N 150
int n;

vector <int> topo;
vector <int> adj[MAX_N + 2];
string word[MAX_N + 2];
int pos[MAX_N + 2];

int vis[MAX_N + 2];

void dfs(int u) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (vis[v] == 0) dfs(v);
        else if (vis[v] == 1) { /// check cycle;
            cout << "NE";
            exit(0);
        }
    }

    vis[u] = 2;
    topo.push_back(u);
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);
    cin >> n;
    FOR(i, 1, n) cin >> word[i];

    FOR(i, 1, n) {
        int x; cin >> x;
        pos[x] = i;
    }

    FOR(i, 1, n) {
        FOR(j, i + 1, n) {
            bool ok = false;
            REP(k, min(SZ(word[i]), SZ(word[j]))) {
                char x = word[i][k], y = word[j][k];
                if (x != y) {
                    if (pos[i] < pos[j]) adj[int(x)].push_back(int(y));
                    else adj[int(y)].push_back(int(x));
                    ok = true;
                    break;
                }
            }

            if (!ok) {
                if (SZ(word[i]) < SZ(word[j]) && pos[i] > pos[j]) return cout << "NE", 0;
                if (SZ(word[i]) > SZ(word[j]) && pos[i] < pos[j]) return cout << "NE", 0;
            }
        }
    }

    memset(vis, 0, sizeof(vis));

    FOR(i, 'a', 'z') if (vis[i] == 0) dfs(i);

    cout << "DA\n";
    reverse(ALL(topo));

    vector <int> f(130, -1);
    int cur = -1;
    for (int x : topo) {
        if (f[x] == -1) f[x] = ++cur;

        for (int v : adj[x]) {
            f[v] = f[x] + 1;
            maximize(cur, f[v]);
        }
    }

    FOR(i, 'a', 'z') cout << (char) (f[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: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10