oj.uz

Submission #81594

# Submission time Handle Problem Language Result Execution time Memory
81594 2018-10-25T13:42:54 Z pzdba Cezar (COCI16_cezar) C++14
20 / 100
 2 ms 736 KB 
#include <bits/stdc++.h>
using namespace std;
string s[105];
bool adj[26][26], adj2[26][26];
int deg[26];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	vector<int> order;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		order.emplace_back(x);
	}
	int pv = 0;
	for(int i=0;i<order.size();i++){
		int idx = order[i];
		if(i != 0){
			int mn = min(s[idx].length(), s[pv].length());
			bool ok = 0;
			for(int j=0;j<mn;j++){
				if(s[idx][j] == s[pv][j]) continue;
				int c1 = s[pv][j]-'a';
				int c2 = s[idx][j]-'a';
				adj[c1][c2] = 1;
				adj2[c1][c2] = 1;
				ok = 1;
				break;
			}
			if(!ok){
				if(mn != s[pv].length()){
					return !printf("NE\n");
				}
			}
		}
		pv = idx;
	}

	for(int k=0;k<26;k++){
		for(int i=0;i<26;i++){
			for(int j=0;j<26;j++){
				adj[i][j] = adj[i][j] | (adj[i][k] & adj[k][j]);
			}
		}
	}
	for(int i=0;i<26;i++){
		for(int j=0;j<26;j++){
			if(adj[i][j] && adj[j][i]) return !printf("NE\n");
			if(adj2[i][j]) deg[j]++;
		}
	}
	queue<int> q;
	for(int i=0;i<26;i++){
		if(deg[i] == 0) q.push(i);
	}
	printf("DA\n");
	while(!q.empty()){
		int u = q.front();
		q.pop();
		printf("%c", u+'a');
		for(int v=0;v<26;v++){
			if(!adj2[u][v]) continue;
			deg[v]--;
			if(deg[v] == 0) q.push(v);
		}
	}
}

Compilation message

cezar.cpp: In function 'int main()':
cezar.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order.size();i++){
              ~^~~~~~~~~~~~~
cezar.cpp:36:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(mn != s[pv].length()){
        ~~~^~~~~~~~~~~~~~~~~

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 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 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 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct

Subtask #7
0 / 10.0

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