oj.uz

Submission #44389

# Submission time Handle Problem Language Result Execution time Memory
44389 2018-04-01T11:59:41 Z JustInCase Cezar (COCI16_cezar) C++17
0 / 100
 2 ms 1260 KB 
#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;
	};

	int32_t cntNodes;
	Node nodes[MAX_N];

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

	void AddEdge(int32_t from, int32_t to) {
		nodes[from].v.push_back(to);
	}
	
	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 = 1; i <= cntNodes; 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++) {
		cin >> words[i].first;
	}

	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 < min(words[i - 1].second.size(), words[i].second.size()); j++) {
			if(words[i - 1].second[j] != words[i].second[j]) {
				foundDiff = true;
				g.AddEdge(words[i - 1].second[j] - 'a' + 1, words[i].second[j] - 'a' + 1);
				break;
			}
		}
	}
	
	if(g.HasCycle()) {
		cout << "NE" << endl;
		return 0;
	}
	
	cout << "DA" << endl;
	g.ComputeNewVals();
	
	for(int32_t i = 1; i <= 26; i++) {
		cout << ans[i]; 
	}
	cout << endl;

	return 0;
}

Compilation message

cezar.cpp: In function 'int main()':
cezar.cpp:116:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int32_t j = 0; j < min(words[i - 1].second.size(), words[i].second.size()); j++) {
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cezar.cpp:115:8: warning: variable 'foundDiff' set but not used [-Wunused-but-set-variable]
   bool foundDiff = false;
        ^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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