Submission #743341

#	Time	Username	Problem	Language	Result	Execution time	Memory
743341		mdobric	Dijamant (COI16_dijament)	C++11	27 / 100	1165 ms	43228 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;

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){
	if (bio[poc] != -1 and povezan[poc][bio[poc]] != 1){
		rez[upit] = -1;
		return;
	}
	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){
				if (povezan[poc][bio[sus[x][i]]] != 1){
					rez[upit] = -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);
	int brojac = 0;
	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);
	int brojac2 = 0;
	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]; j++){
				bfs2(m2[t[i][j]], i);
			}
			//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:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i = 0; i < sus[x].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~
dijament.cpp: In function 'void bfs2(int, int)':
dijament.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   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