Submission #1023971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023971		rxlfd314	Cezar (COCI16_cezar)	C++17	10 / 100	1 ms	352 KiB

cezar

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
using arl4 = array<ll, 4>;
 
#define vt vector
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
void solve();

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int T = 1;
  //cin >> T;
  FOR(t, 1, T) {
    solve();
  }
}

constexpr int MOD = 998244353;

void solve() {
  int N;
  cin >> N;
  vt<string> A(N);
  for (auto &i : A)
    cin >> i;
  vt<int> ord(N);
  for (int &i : ord)
    cin >> i, i--;
  
  vt<vt<int>> adj(26);
  FOR(ii, 0, N-1)
    FOR(jj, ii+1, N-1) {
      const int i = ord[ii], j = ord[jj];
      const int s = min(size(A[i]), size(A[j]));
      int k = 0;
      while (k < s && A[i][k] == A[j][k])
        k++;
      if (k < s)
        adj[A[i][k] - 'a'].push_back(A[j][k] - 'a');
      if (k == s && size(A[i]) > size(A[j])) {
        cout << "NE\n";
        return;
      }
    }
  
  vt<int> status(26);
  function<bool(int)> cyc = [&](int i) {
    status[i] = 2;
    for (int j : adj[i]) {
      if (status[j] == 1)
        continue;
      if (status[j] == 2 || cyc(j))
        return true;
    }
    status[i] = 1;
    return false;
  };
  
  FOR(i, 0, 25)
    if (!status[i] && cyc(i)) {
      cout << "NE\n";
      return;
    }
  
  vt<int> tso;
  vt<bool> seen(26);
  int x = 0;
  function<void(int)> top_sort = [&](int i) {
    seen[i] = true;
    for (int j : adj[i])
      if (!seen[j])
        top_sort(j);
    tso.push_back(i);
  };
  FOR(i, 0, 25)
    if (!seen[i])
      top_sort(i), x++;
  
  reverse(all(tso));
  assert(size(tso) == 26);
  vt<char> ans(26);
  FOR(i, 0, 25)
    ans[tso[i]] = 'a' + i;
  
  cout << "DA\n";
  for (char &i : ans)
    cout << i;
  cout << '\n';
}

• 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