Submission #81594

#	Time	Username	Problem	Language	Result	Execution time	Memory
81594		pzdba	Cezar (COCI16_cezar)	C++14	20 / 100	2 ms	736 KiB

cezar

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10