Submission #1194457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194457		nquang	Cezar (COCI16_cezar)	C++17	70 / 100	1 ms	328 KiB

cezar

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
set<int> adj[N];
short int vst[N];
string s[N];
int p[N];
char ch[26];
vector<int> topo;
bool cycle = 0;
void dfs(int u);

int main (int argc, char const *argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;	
	for(int i = 1; i <= n; ++i) cin >> s[i];
	for(int i = 1; i <= n; ++i) cin >> p[i];
	memset(ch, 0, sizeof(ch));
	vector<string> arr;
	for(int i = 1; i <= n; ++i) arr.push_back(s[p[i]]);
	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			bool g = 0;
			for(int id = 0; id < arr[i].length() && id < arr[j].length(); ++id){
				if(arr[i][id] != arr[j][id]){
					adj[arr[i][id] - 'a'].insert(arr[j][id] - 'a');
					g = 1;
					break;
				}
			}
			if(g) continue;
			if(arr[i].length() > arr[j].length()){
				cout << "NE";
				return 0;
			}
		}
	}
	for(int i = 0; i < 26; ++i){
		if(vst[i] == 0 && adj[i].size()) dfs(i);
	}
	if(cycle) {
		cout << "NE";
		return 0;
	}
	reverse(topo.begin(), topo.end());
	char c = 'a';
	for(int x : topo){
		ch[x] = c++;
	}
	cout << "DA\n";
	for(int i = 0; i < 26; ++i) cout << (ch[i] == 0 ? c++ : ch[i]);
	return 0;
}
void dfs(int u){
	if(cycle) return;
	if(vst[u] == 2) return;
	if(vst[u] == 1){
		cycle = 1;
		return;
	}
	vst[u] = 1;
	for(int v : adj[u]){
		dfs(v);
	}
	vst[u] = 2;
	topo.push_back(u);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10