Rezultati

Up. imeNalogaJezikRezultatČas oddaje
fedja-2017 Prijateljske besede C++ 100/100OK 20. apr '17 @ 19:41

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,195 MiB 0,004 s OK
#2 12/12 3,285 MiB 0,004 s OK
#3 12/12 3,691 MiB 0,022 s OK
#4 12/12 3,770 MiB 0,022 s OK
#5 13/13 3,820 MiB 0,022 s OK
#6 13/13 3,801 MiB 0,022 s OK
#7 13/13 4,039 MiB 0,022 s OK
#8 13/13 3,801 MiB 0,022 s OK

Ocenjevani program (besede.cpp):
#include <cstdio>
#include <iostream>
#include <cstdint>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstring>
using namespace std;

struct word_entry {
	word_entry(char *word):beseda(word), predpona(word, 3),
	  pripona(word, strlen(word) - 3, 100)
	{}	

	string predpona;
	string pripona;
	string beseda;
};

typedef map<string, list<int>> Mapa;

static void vstavi (Mapa &mapa, string& pona, int kaj)
{
	Mapa::iterator it = mapa.find (pona);
	if (mapa.end() == it) {
		list<int> entry {kaj};
		mapa.emplace (pona, entry);
	} else {
		list<int>& entry = it->second;
		entry.push_back (kaj);
	}
}

struct stack_entry {
	stack_entry (string s, bool p):pona(s), je_pripona(p) {}
	std::string pona;
	bool je_pripona;
};

int main()
{
	int N;
	int sr = scanf ("%d", &N);

	vector<word_entry> besede;
	vector<bool> visited;

	Mapa predpone;
	Mapa pripone;

	

	char* beseda = new char[12];
	for (int i = 0; i < N; ++i) {
		sr = scanf ("%s", beseda);
		if (sr != 1)
			throw runtime_error ("BLah");

		besede.emplace_back (beseda);
		visited.push_back (false);
		word_entry &bes = besede.back();
//		cout << " Pre: " << bes.predpona << " Pri: " << bes.pripona
//			 << " beseda: " << bes.beseda << endl; 

		// Vstavi
		vstavi (predpone, bes.predpona, i);
		vstavi (pripone, bes.pripona, i);

	}

	stack<stack_entry> sklad;
	sklad.emplace (besede.front().pripona, true);
	sklad.emplace (besede.front().predpona, false);
	int st_prijateljev = 0;

	while (! sklad.empty()) {
		stack_entry s = sklad.top(); sklad.pop();

		if (s.je_pripona) {
			Mapa::iterator it = pripone.find (s.pona);
			if (pripone.end() != it) { // Sprocesiraj vse besede in vstavi predpone (pripona bo ista)
				for (int index : it->second) {
//					cout << "Processing index " << index << endl;
					if (visited[index])
						continue;
					visited[index] = true;
					st_prijateljev ++;
					sklad.emplace (besede[index].predpona, false);
				}
			}
		} else {// (!s.je_pripona)
			Mapa::iterator it = predpone.find (s.pona);
			if (predpone.end() != it) { // Sprocesiraj vse besede in vstavi pripone (predpona bo ista)
				for (int index : it->second) {
//					cout << "Processing index " << index << endl;
					if (visited[index])
						continue;
					visited[index] = true;
					st_prijateljev ++;
					sklad.emplace (besede[index].pripona, true);
				}
			}
		}
	}

	cout << st_prijateljev << endl;
}