Submission #743378

#	Time	Username	Problem	Language	Result	Execution time	Memory
743378		mdobric	Dijamant (COI16_dijament)	C++11	27 / 100	2065 ms	40512 KiB

dijament

#include <bits/stdc++.h>
using namespace std;

int n;
string s[1005];
string t[1005][1005];
int k[1005];
map <string, int> m, m2;
int deklariran[100005];
int povezan[1005][1005];
int rez[1005];
vector <int> sus[1005];
int bio[1005];
queue <int> q;
int brojac = 0, brojac2 = 0;

void bfs (int poc){
	bio[poc] = 0;
	q.push(poc);
	while (!q.empty()){
		int x = q.front();
		q.pop();
		if (x != poc){
			povezan[x][poc] = 1;
			povezan[poc][x] = 1;
		}
		for (int i = 0; i < sus[x].size(); i++){
			if (bio[sus[x][i]] == -1){
				bio[sus[x][i]] = 0;
				q.push(sus[x][i]);
			}
		}
	}
	return;
}

void bfs2 (int poc, int upit, int prvi){
	bio[poc] = poc;
	q.push(poc);
	while (!q.empty()){
		int x = q.front();
		q.pop();
		for (int i = 0; i < sus[x].size(); i++){
			if (bio[sus[x][i]] == -1){
				bio[sus[x][i]] = poc;
				q.push(sus[x][i]);
			}
			else
			if (bio[sus[x][i]] != -1 and bio[sus[x][i]] != poc){
				rez[upit] = -1;
			}
		}
	}
	if (prvi == 1){
		for (int i = 0; i < brojac2; i++){
			if (bio[i] == poc){
				bio[i] = -1;
			}
		}
	}
	
	
	return;
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie();
	cin >> n;
	for (int i = 0; i < n; i++){
		//ulaz
		cin >> s[i];
		m[s[i]] = -1;
		m2[s[i]] = -1;
		string dv;
		cin >> dv;
		int j = -1;
		do{
			j++;
			cin >> t[i][j];
			m[t[i][j]] = -1;
			m2[t[i][j]] = -1;
		} while (t[i][j] != ";");
		k[i] = j;
	}
	memset(deklariran, 0, sizeof deklariran);
	for (int i = 0; i < n; i++){
		//uvođenje oznaka
		if (m[s[i]] == -1){
			m[s[i]] = brojac;
			brojac++;
		}
		int j = -1;
		do{
			j++;
			if (m[t[i][j]] == -1 and t[i][j] != ";"){
				m[t[i][j]] = brojac;
				brojac++;
			}
		} while (t[i][j] != ";");
	}
	for (int i = 0; i < n; i++){
		//provjeravamo prva 2 uvjeta
		if (deklariran[m[s[i]]] == 1){
			rez[i] = -1;
		}
		else{
			for (int j = 0; j < k[i]; j++){
				if (deklariran[m[t[i][j]]] == 0){
					rez[i] = -1;
					break;
				}
			}
		}
		if (rez[i] != -1){
			deklariran[m[s[i]]] = 1;
		}		
	}
	memset(deklariran, 0, sizeof deklariran);
	for (int i = 0; i < n; i++){
		//ponovno uvodimo oznake za one koji zadovoljavaju prva dva uvjeta
		if (rez[i] == 0){
			if (m2[s[i]] == -1){
				m2[s[i]] = brojac2;
				brojac2++;
			}
			int j = -1;
			do{
				j++;
				if (m2[t[i][j]] == -1){
					m2[t[i][j]] = brojac2;
					brojac2++;
				}
			} while (t[i][j] != ";");
		}
	}
	for (int i = 0; i < n; i++){
		//provjeravamo prva 2 uvjeta
		if (deklariran[m2[s[i]]] == 1){
			rez[i] = -1;
		}
		else{
			for (int j = 0; j < k[i]; j++){
				if (deklariran[m2[t[i][j]]] == 0){
					rez[i] = -1;
					break;
				}
			}
		}
		//cout << "  " << rez[i] << endl;	
		if (rez[i] == 0){
			//cout << s[i] << endl;
			deklariran[m2[s[i]]] = 1;
			//povezujemo dodani čvor sa susjedima
			for (int j = 0; j < k[i]; j++){
				sus[m2[s[i]]].push_back(m2[t[i][j]]);
			}
			memset(bio, -1, sizeof bio);
			bfs(m2[s[i]]);
			//provjeravamo stvara li se dijamant
			memset(bio, -1, sizeof bio);
			for (int j = 0; j < k[i] - 1; j++){
				bfs2(m2[t[i][j]], i, 0);
				for (int j2 = j + 1; j2 < k[i]; j2++){
					if (povezan[m2[t[i][j]]][m2[t[i][j2]]] == 0){
						bfs2(m2[t[i][j2]], i, 1);
					}
				}
				for (int j2 = 0; j2 < brojac2; j2++){
					bio[j2] = -1;
				}
			}
			//ako treci uvjet nije zadovoljen, micemo povezano, deklariran, i sus
			if (rez[i] == -1){
				sus[m2[s[i]]].clear();
				deklariran[m2[s[i]]] = 0;
				for (int j = 0; j < brojac2; j++){
					povezan[m2[s[i]]][j] = 0;
					povezan[j][m2[s[i]]] = 0;
				}
			}
		}
	}
	for (int i = 0; i < n; i++){
		if (rez[i] == -1){
			cout << "greska" << "\n";
		}
		else{
			cout << "ok" << "\n";
		}
	}
	
	return 0;
}

Compilation message (stderr)

dijament.cpp: In function 'void bfs(int)':
dijament.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < sus[x].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~
dijament.cpp: In function 'void bfs2(int, int, int)':
dijament.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < sus[x].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44