oj.uz

Submission #88048

# Submission time Handle Problem Language Result Execution time Memory
88048 2018-12-03T14:53:07 Z jasony123123 Cezar (COCI16_cezar) C++11
20 / 100
 3 ms 1412 KB 
#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

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.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1068 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 1196 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 1196 KB Output is correct
2 Correct 3 ms 1196 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #10
0 / 10.0

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