# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
162669 | 2019-11-09T07:58:19 Z | _qVp_ | Cezar (COCI16_cezar) | C++14 | 11 ms | 564 KB |
#include <bits/stdc++.h> using namespace std; const int md = 105; const int oo = 1e9; int low[md], num[md], a[md], ans[md]; stack < int > st, topo; vector < int > adj[md]; int cnt, n; string s1[md], s[md]; void tarjan(int u) { st.push(u); low[u] = num[u] = ++cnt; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (num[v]) low[u] = min(low[u], num[v]); else { tarjan(v); low[u] = min(low[u], low[v]); } } if (low[u] == num[u]) { int v = 0, c = 0; do { v = st.top(); st.pop(); c++; low[u] = num[u] = oo; } while (v != u); if (c >= 2) { cout << "NE"; exit(0); } } topo.push(u); } int main() { freopen("test.in", "r", stdin); ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> s1[i]; for(int i = 1; i <= n; i++) { int x; cin >> x; s[i] = s1[x]; } for(int u = 1; u <= n; u++) { //int u = a[i]; //cerr << s[u] << endl; for(int v = u + 1; v <= n; v++) { int len = min(s[u].size(), s[v].size()); //cerr << s[v] << " "; bool ok = false; for(int k = 0; k < len; k++) if (s[u][k] != s[v][k]) { ok = true; //cout << s[u][k] - 'a' << " " << s[v][k] - 'a' << endl; adj[s[u][k] - 'a'].push_back(s[v][k] - 'a'); break; } if (ok == false && s[u].size() > s[v].size()) { cout << "NE"; return 0; } } //cerr << endl; } //cerr << "checking"; for(int i = 0; i < 26; i++) if (!num[i]) tarjan(i); int cnt = 0; while (topo.size()) { int u = topo.top(); topo.pop(); //cout << char(u + 'a') << " "; ans[u] = cnt++; } cout << "DA\n"; for(int i = 0; i < 26; i++) cout << char(ans[i] + 'a'); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 564 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 420 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |