oj.uz

Submission #98265

# Submission time Handle Problem Language Result Execution time Memory
98265 2019-02-21T18:05:36 Z dalgerok Cezar (COCI16_cezar) C++17
80 / 100
 14 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 105, M = 26;




int n, cl[N];
int a[M][M], in[M];
string s[N], t[N];
vector < int > g[N], order;
char ans[M];


void dfs1(int v){
    if(cl[v] == 1){
        cout << "NE";
        exit(0);
    }
    cl[v] = 1;
    for(int to = 0; to < M; to++){
        if(a[v][to]){
            dfs1(to);
        }
    }
    cl[v] = 0;
}

void dfs2(int v){
    cl[v] = 1;
    for(int to = 0; to < M; to++){
        if(a[v][to] && !cl[to]){
            dfs2(to);
        }
    }
    order.push_back(v);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        for(auto &it : s[i]){
            it -= 'a';
        }
    }
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        t[i] = s[x];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if((int)t[i].size() < (int)t[j].size() && t[j].substr(0, (int)t[i].size()) == t[i]){
                return cout << "NE", 0;
            }
        }
    }
    for(int i = 2; i <= n; i++){
        for(int j = 0; j < min((int)t[i - 1].size(), (int)t[i].size()); j++){
            if(t[i - 1][j] != t[i][j]){
                if(a[t[i][j]][t[i - 1][j]] == 0){
                    a[t[i][j]][t[i - 1][j]] = 1;
                    in[t[i - 1][j]] += 1;
                }
                break;
            }
        }
    }
    for(int i = 0; i < M; i++){
        memset(cl, 0, sizeof(cl));
        dfs1(i);
    }
    memset(cl, 0, sizeof(cl));
    for(int i = 0; i < M; i++){
        if(in[i] == 0){
            dfs2(i);
        }
    }
    for(int i = 0; i < M; i++){
        ans[order[i]] = i;
    }
    cout << "DA\n";
    for(int i = 0; i < M; i++){
        cout << char(ans[i] + 'a');
    }
}

Compilation message

cezar.cpp: In function 'int main()':
cezar.cpp:65:29: warning: array subscript has type 'char' [-Wchar-subscripts]
                 if(a[t[i][j]][t[i - 1][j]] == 0){
                             ^
cezar.cpp:65:42: warning: array subscript has type 'char' [-Wchar-subscripts]
                 if(a[t[i][j]][t[i - 1][j]] == 0){
                                          ^
cezar.cpp:66:30: warning: array subscript has type 'char' [-Wchar-subscripts]
                     a[t[i][j]][t[i - 1][j]] = 1;
                              ^
cezar.cpp:66:43: warning: array subscript has type 'char' [-Wchar-subscripts]
                     a[t[i][j]][t[i - 1][j]] = 1;
                                           ^
cezar.cpp:67:35: warning: array subscript has type 'char' [-Wchar-subscripts]
                     in[t[i - 1][j]] += 1;
                                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -