Submission #44391

#	Time	Username	Problem	Language	Result	Execution time	Memory
44391		JustInCase	Cezar (COCI16_cezar)	C++17	20 / 100	2 ms	520 KiB

cezar

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int32_t MAX_N = 105;

pair< int32_t, string > words[MAX_N];
char ans[MAX_N];

class Graph {
private:
	class Node {
	public:
		bool isVisited;
		vector< int32_t > v;
	};
	
	bool hasEdge[MAX_N][MAX_N];
	int32_t cntNodes;
	Node nodes[MAX_N];

public:
	void Init(int32_t n) {
		cntNodes = n;
	}

	void AddEdge(int32_t from, int32_t to) {
		if(!hasEdge[from][to]) {
			nodes[from].v.push_back(to);
			hasEdge[from][to] = true;
		}
	}
	
	bool DfsCheckCycle(int32_t node) {
		nodes[node].isVisited = true;

		for(int32_t x : nodes[node].v) {
			if(nodes[x].isVisited) {
				return true;
			}

			if(DfsCheckCycle(x)) {
				return true;
			}
		}

		return false;
	}

	void MarkAllNodesUnvisited() {
		for(int32_t i = 1; i <= cntNodes; i++) {
			nodes[i].isVisited = false;
		}
	}

	bool HasCycle() {
		for(int32_t i = 1; i <= cntNodes; i++) {
			MarkAllNodesUnvisited();
			if(DfsCheckCycle(i)) {
				return true;
			}
		}

		return false;
	}

	void DfsTopoSort(int32_t node, stack< int32_t > &topoSort) {
		nodes[node].isVisited = true;

		for(int32_t x : nodes[node].v) {
			if(!nodes[x].isVisited) {
				DfsTopoSort(x, topoSort);
			}
		}

		topoSort.push(node);
	}

	void ComputeNewVals() {
		MarkAllNodesUnvisited();
		stack< int32_t > st;

		for(int32_t i = cntNodes; i >= 1; i--) {
			if(!nodes[i].isVisited) {
				DfsTopoSort(i, st);
			}
		}
		
		char curr = 'a';
		while(!st.empty()) {
			ans[st.top()] = curr;
			curr++;
			st.pop();
		}
	}
};

Graph g;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int32_t n;
	cin >> n;

	for(int32_t i = 1; i <= n; i++) {
		cin >> words[i].second;
	}

	for(int32_t i = 1; i <= n; i++) {
		int32_t a;
		cin >> a;

		words[a].first = i;
	}

	sort(words + 1, words + 1 + n);
	
	g.Init(26);
	for(int32_t i = 2; i <= n; i++) {
		bool foundDiff = false;
		for(int32_t j = 0; j < (int32_t) min(words[i - 1].second.size(), words[i].second.size()); j++) {
			if(words[i - 1].second[j] != words[i].second[j]) {
				g.AddEdge(words[i - 1].second[j] - 'a' + 1, words[i].second[j] - 'a' + 1);
				foundDiff = true;
				break;
			}
		}

		if(!foundDiff && words[i - 1].second.size() > words[i].second.size()) {
			cout << "NE" << endl;
			return 0;
		}
	}

	if(g.HasCycle()) {
		cout << "NE" << endl;
		return 0;
	}
	
	for(int32_t i = 1; i <= 26; i++) {
		ans[i] = '1';
	}
	
	cout << "DA" << endl;
	g.ComputeNewVals();
	
	for(int32_t i = 1; i <= 26; i++) {
		cout << ans[i]; 
	}
	cout << endl;

	return 0;
}

• 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