oj.uz

Submission #133421

# Submission time Handle Problem Language Result Execution time Memory
133421 2019-07-20T15:00:50 Z tdwn Cezar (COCI16_cezar) C++17
0 / 100
 3 ms 376 KB 
    #include <bits/stdc++.h>
    #define ll long long 
    #define pb push_back
    #define mp make_pair
    using namespace std;
    const int maxn = 110;
    string tempstr[maxn];
    string str[maxn];
    int perm[maxn], n;
     
    vector<int>g[30], rg[30];
    int visited[maxn];
    vector<int>order;
     
    bool cycle;
    bool edge[maxn][maxn];
     
    int res[maxn];

    void dfs(int node) {
    	if(visited[node] == 2) return;
    	if(visited[node] == 1) {
    		cycle = true;
    		return;
    	}
     
    	visited[node] = 1;
    	for(int i:g[node]) {
    		if(visited[i] == 0) {
    			dfs(i);
    		}
    		else if(visited[i] == 1) {
    			cycle = true;
    		}
    	}
     
    	visited[node] = 2;
    	order.pb(node);
    }
     
    int main() {
    	cin>>n;
    	for(int i=1;i<=n;i++) {
    		cin>>tempstr[i];
    	}
    	for(int i=1;i<=n;i++) {
    		cin>>perm[i];
    	}
    	for(int i=1;i<=n;i++) {
    		str[i] = tempstr[perm[i]];
    	}
     
    	for(int i=1;i<=n;i++) {
    		for(int j=i+1;j<=n;j++) {
    			if(str[j].length() < str[i].length()) {
    				if(str[i].substr(0, str[j].length()) == str[j]) {
    					cout<<"NE\n";
    					return 0;
    				}
    			}
    		}
    	}
     
    	for(int i=1;i<=n;i++) {
    		for(int j=i+1;j<=n;j++) {
    			for(int k=0;k<min(int(str[i].length()), int(str[j].length()));k++) {
    				if(str[i][k] != str[j][k]) {
    					edge[int(str[i][k]-'a')][int(str[j][k]-'a')] = true;
    					break;
    				}
    			}
    		}
    	}
     
    	for(int i=0;i<26;i++) {
    		for(int j=0;j<26;j++) {
    			if(edge[i][j]) g[i].pb(j);
    		}
    	}
     
    	for(int i=25;i>=0;i--) {
    		if(visited[i] == 0) dfs(i);
    	}
     
    	if(cycle) {
    		cout<<"NE\n";
    		return 0;
    	}
     
    	cout<<"DA\n";
    	reverse(order.begin(), order.end());
    	for(int i=0;i<order.size();i++) {
    		res[order[i]] = i;
    	}
    	for(int i=0;i<n;i++) {
    		cout<<int(res[i]+'a');
    	}
    }

Compilation message

cezar.cpp: In function 'int main()':
cezar.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<order.size();i++) {
                  ~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
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 #4
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 #5
0 / 10.0

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

Subtask #6
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 #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 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 376 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 376 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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -