oj.uz

Submission #33077

# Submission time Handle Problem Language Result Execution time Memory
33077 2017-10-19T23:38:47 Z trath Cezar (COCI16_cezar) C++14
60 / 100
 0 ms 2184 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ieps (int) 1e6
#define eps (int) 1e9
#define pii pair<int,int>
// Introduction et Rondo Capriccioso :)
vector<char> adj[27];
set<char > cccc;
int sz[27];
int32_t main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<string> s(n);
	for(int i = 0;i<n;i++) cin>>s[i];
	vector<int> ord(n);
	for(int i = 0;i<n;i++) cin>>ord[i];
	for(int i = 0;i<n - 1;i++){
		string f = s[ord[i] - 1] ,  t = s[ord[i+1] - 1];
		int mismatch = -1;
		for(int i = 0; i<min(f.size() , t.size()) ; i++){
			if(f[i] != t[i]){
				mismatch = i;
				break;
			}
		}
		//cout<<mismatch<<endl;
		if(mismatch == -1 && f.size() != t.size()){
			if(f.size() < t.size()) continue;
			cout<<"NE"<<endl;
			return 0;
		}
		else{
			adj[f[mismatch] - 'a'].pb(t[mismatch] - 'a');
			//cout<<f[mismatch]<<" "<<t[mismatch]<<endl;
			cccc.insert(f[mismatch]) , cccc.insert(t[mismatch]);
			sz[t[mismatch] - 'a']++;
		}
	}
	int cnt = 0LL;
	char curr = 'a';
	string ans;
	for(int i = 0;i<26;i++) ans += ' ';
	queue<int> q;
	for(auto ttt : cccc){
		if(sz[ttt - 'a'] == 0) q.push(ttt - 'a');
	}
	while(!q.empty()){
		ans[q.front()] = curr++;
		int u = q.front();
		q.pop();
		cnt++;
		for(auto tt : adj[u]){
			sz[tt]--;
			if(sz[tt] == 0) q.push(tt);
		}
	}
	if(cnt != cccc.size()){
		cout<<"NE"<<endl;
		return 0;
	}
	for(int i = 0;i<26;i++){
		if(ans[i] == ' ') ans[i] = curr++;
	}
		cout<<"DA"<<endl<<ans<<endl;
}

Compilation message

cezar.cpp: In function 'int32_t main()':
cezar.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<min(f.size() , t.size()) ; i++){
                   ^
cezar.cpp:58:9: warning: array subscript has type 'char' [-Wchar-subscripts]
    sz[tt]--;
         ^
cezar.cpp:59:12: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(sz[tt] == 0) q.push(tt);
            ^
cezar.cpp:62:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cnt != cccc.size()){
         ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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