# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
83452 | Genezio | Cezar (COCI16_cezar) | C++14 | 1088 ms | 464 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 pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define ll long long
const int N = 110;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
string s[N];
vector<int> v[30];
int a[N];
int deg[30];
int ans[N];
bool e[N][N];
int main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
int n;
int c=0;
cin>>n;
for(int i=0;i<n;i++) {
cin>>s[i];
}
for(int i=0;i<n;i++) {
cin>>a[i];
a[i]--;
}
for(int i=0;i<n-1;i++) {
int idx=0;
while(true) {
if(s[a[i]][idx]==s[a[i+1]][idx]) {
if(s[a[i]].size()==idx+1) break;
if(s[a[i+1]].size()==idx+1) break;
} else {
if(!e[(int)(s[a[i]][idx]-'a')][(int)(s[a[i+1]][idx]-'a')]) {
v[(int)(s[a[i]][idx]-'a')].push_back((int)(s[a[i+1]][idx]-'a'));
e[(int)(s[a[i]][idx]-'a')][(int)(s[a[i+1]][idx]-'a')]=true;
}
deg[(int)(s[a[i+1]][idx]-'a')]++;
break;
}
}
}
queue<int> q;
for(int i=0;i<26;i++) {
if(!deg[i]) q.push(i);
}
while(q.size()) {
int at = q.front();
q.pop();
ans[at]=c;
c++;
//cout<<at<<"\n";
for(int i=0;i<v[at].size();i++) {
deg[v[at][i]]--;
//cout<<v[at][i]<<" "<<deg[v[at][i]]<<"\n";
if(!deg[v[at][i]]) q.push(v[at][i]);
}
}
if(c<26) {
cout<<"NE\n";
} else {
cout<<"DA\n";
for(int i=0;i<26;i++) {
cout<<(char)(ans[i]+(int)('a'));
}
cout<<"\n";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |