Submission #88048

#	Time	Username	Problem	Language	Result	Execution time	Memory
88048		jasony123123	Cezar (COCI16_cezar)	C++11	20 / 100	3 ms	1412 KiB

cezar

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.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) for (int j : adj[i])
		prereq[j] += i + 1;

	queue<int> q;
	FOR(i, 0, 26)
		if (prereq[i] == 0)
			q.push(i);
	while (!q.empty()) {
		topsort.push_back(q.front());
		int used = q.front();
		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 - 1) {
		int letterDif = all[i].cmp(all[i + 1]);
		if (letterDif == -1) {
			if (all[i].str.size() > all[i + 1].str.size())
				return 0;
		}
		else {
			adj[all[i].str[letterDif] - 'a'].push_back(all[i + 1].str[letterDif] - 'a');
		}
	}
	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();
	if(!genAdj()){
		cout << "NE\n";
	}
	else {
		if (!topo())
			cout << "NE\n";
		else {
			cout << "DA\n";
			FOR(i, 0, 26)
				cout << (char)(topsort[i] + 'a');
			cout << "\n";
		}
	}
	return 0;
}


void io() {
#ifdef LOCAL_STUFF
	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 (stderr)

cezar.cpp: In member function 'int fastStr::cmp(fastStr&)':
cezar.cpp:51: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:51: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
• 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