oj.uz

답안 #743341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743341 2023-05-17T10:01:47 Z mdobric Dijamant (COI16_dijament) C++11
27 / 100
 1165 ms 43228 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32332 KB Output is correct
2 Correct 18 ms 32340 KB Output is correct
3 Correct 17 ms 32340 KB Output is correct
4 Correct 17 ms 32404 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32332 KB Output is correct
2 Correct 18 ms 32340 KB Output is correct
3 Correct 17 ms 32340 KB Output is correct
4 Correct 17 ms 32404 KB Output is correct
5 Correct 18 ms 32296 KB Output is correct
6 Correct 21 ms 32884 KB Output is correct
7 Correct 19 ms 32588 KB Output is correct
8 Correct 18 ms 32468 KB Output is correct
9 Correct 21 ms 32468 KB Output is correct
10 Correct 17 ms 32524 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32332 KB Output is correct
2 Correct 18 ms 32340 KB Output is correct
3 Correct 17 ms 32340 KB Output is correct
4 Correct 17 ms 32404 KB Output is correct
5 Correct 18 ms 32296 KB Output is correct
6 Correct 21 ms 32884 KB Output is correct
7 Correct 19 ms 32588 KB Output is correct
8 Correct 18 ms 32468 KB Output is correct
9 Correct 21 ms 32468 KB Output is correct
10 Correct 17 ms 32524 KB Output is correct
11 Correct 21 ms 32468 KB Output is correct
12 Incorrect 17 ms 32620 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1030 ms 42664 KB Output is correct
2 Correct 1165 ms 43228 KB Output is correct
3 Correct 283 ms 36836 KB Output is correct
4 Incorrect 38 ms 34456 KB Output isn't correct
5 Halted 0 ms 0 KB -