oj.uz

Submission #81495

# Submission time Handle Problem Language Result Execution time Memory
81495 2018-10-25T04:09:12 Z ngot23 Cezar (COCI16_cezar) C++11
0 / 100
 3 ms 620 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=30;
vector <int > g[N];
string s1[105], s2[105];
int n, visit[N], in[N], cur, c[N], dd[N][N];
bool cycle=0;

void DFS(int u) {
    if(cycle) return;
    visit[u]=1;
    for(int v:g[u]) {
        if(visit[v]==0) {
            DFS(v);
        } else if(visit[v]==1) { cycle=1; return; }
    }
    visit[u]=2;
}

void DFS2(int u) {
    c[u]=cur++;
    for(int v:g[u]) {
        DFS2(v);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n;
    rep(i, 1, n) cin >> s1[i];
    rep(i, 1, n) {
        int u; cin >> u;
        s2[i]=s1[u];
    }
    for(int i=1 ; i<n ; ++i) {
        int leng=min(s2[i].size(), s2[i+1].size())-1;

        rep(j, 0, leng) {
            if(s2[i][j]!=s2[i+1][j]) {
                int u=s2[i][j]-'a';
                int v=s2[i+1][j]-'a';
                if(!dd[u][v]) {
                        g[u].push_back(v);
                        dd[u][v]=1;
                }
                ++in[v];
                break;
            }
        }
    }
    rep(i, 0, 25) {
        if(g[i].size()==0||visit[i]) continue;
        cycle=0;
        DFS(i);
        if(cycle) return cout << "NE\n", 0;
    }
    rep(i, 0, 25) {
        if(!in[i]) DFS2(i);
    }
    cout << "DA\n";
    rep(i, 0, 25) {
        cout << (char)(c[i]+'a');
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 500 KB Output is correct
2 Incorrect 2 ms 500 KB Output isn't correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 516 KB Output is correct
2 Incorrect 2 ms 532 KB Output isn't correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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