oj.uz

Submission #88122

# Submission time Handle Problem Language Result Execution time Memory
88122 2018-12-03T21:17:39 Z jasony123123 Cezar (COCI16_cezar) C++11
40 / 100
 3 ms 1044 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

struct fastStr {
	string str;
	int cmp(fastStr & other) { // returns idx of first different or -1 if no differnet
		for (int i = 0; i < str.size() && i < other.str.size(); i++)
			if (str[i] != other.str[i])
				return i;
		return -1;
	}
};

int N;
v<fastStr> all;
v<int> adj[26]; // a->b ::  a<b
v<int> topsort;
int prereq[26];

bool topo() { // topological sort a->b st a before b
	FOR(i, 0, 26) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
		for (int j : adj[i]) {
			prereq[j] += i + 1;
		//	cout << (char)(i + 'a') << " before " << (char)(j + 'a') << "\n";
		}
	}

	priority_queue<int, vector<int>, greater<int>> q;
	FOR(i, 0, 26)
		if (prereq[i] == 0)
			q.push(i);
	while (!q.empty()) {
		topsort.push_back(q.top());
		int used = q.top();
		q.pop();

		for (int j : adj[used]) {
			prereq[j] -= used + 1;
			if (prereq[j] == 0)
				q.push(j);
		}
	}
	return topsort.size() == 26;
}

bool genAdj() {
	FOR(i, 0, N) {
		FOR(j, i + 1, N) {
			int letterDif = all[i].cmp(all[j]);
			if (letterDif == -1) {
				if (all[i].str.size() > all[j].str.size())
					return 0;
			}
			else {
				adj[all[i].str[letterDif] - 'a'].push_back(all[j].str[letterDif] - 'a');
				//	pf("%c < %c \n", all[i].str[letterDif], all[j].str[letterDif]);
			}
		}
	}
	return 1;
}

void input() {
	cin >> N;
	v<fastStr> temp(N);
	all.resize(N);
	FOR(i, 0, N)
		cin >> temp[i].str;
	FOR(i, 0, N) {
		int which;
		cin >> which;
		all[i] = temp[which - 1];
	}
}

int main() {
	io();
	input();
	//for (fastStr s : all)
	//	cout << s.str << "\n";

	if (!genAdj()) {
		cout << "NE\n";
	}
	else {
		if (!topo())
			cout << "NE\n";
		else {
			cout << "DA\n";
			char ans[26];
			FOR(i, 0, 26)
				ans[topsort[i]] = i;
			FOR(i, 0, 26)
				cout << (char)(ans[i] + 'a');
			cout << "\n";
		}
	}
	return 0;
}


void io() {
#ifdef LOCAL_PROJECT
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message

cezar.cpp: In member function 'int fastStr::cmp(fastStr&)':
cezar.cpp:29:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < str.size() && i < other.str.size(); i++)
                   ~~^~~~~~~~~~~~
cezar.cpp:29:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < str.size() && i < other.str.size(); i++)
                                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 716 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 872 KB Output is correct
2 Correct 3 ms 1044 KB Output is correct

Subtask #8
0 / 10.0

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