| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 33073 | trath | Cezar (COCI16_cezar) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ieps (int) 1e6
#define eps (int) 1e9
#define pii pair<int,int>
// Introduction et Rondo Capriccioso :)
vector<char> adj[27];
int sz[27];
int32_t main(){
ios_base::sync_with_stdio(false);
int n;
cin>>n;
vector<string> s(n);
for(int i = 0;i<n;i++) cin>>s[i];
vector<int> ord(n);
for(int i = 0;i<n;i++) cin>>ord[i];
for(int i = 0;i<n - 1;i++){
string f = s[ord[i] - 1] , t = s[ord[i+1] - 1];
int mismatch = -1;
for(int i = 0; i<min(f.size() , t.size()) ; i++){
if(f[i] != t[i]){
mismatch = i;
break;
}
}
//cout<<mismatch<<endl;
if(mismatch == -1 && f.size() != t.size()){
if(f.size() < t.size()) continue;
cout<<"NE"<<endl;
return 0;
}
else{
adj[f[mismatch] - 'a'].pb(t[mismatch] - 'a');
//cout<<f[mismatch]<<" "<<t[mismatch]<<endl;
sz[t[mismatch] - 'a']++;
}
}
string ans;
queue<int> q;
for(int i = 0;i<26;i++){
if(sz[i] == 0) q.push(i);
}
while(!q.empty()){
ans += q.front() + 'a';
int u = q.front();
q.pop();
for(auto tt : adj[u]){
sz[tt]--;
if(sz[tt] == 0) q.push(tt);
}
}
//cout<<ans<<endl;
if(ans.size() == 26){
cout<<"DA"<<endl<<ans<<endl;
}
else{
cout<<"NE"<<endl;
}
}