답안 #743378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743378 2023-05-17T10:53:52 Z mdobric Dijamant (COI16_dijament) C++11
27 / 100
2000 ms 40512 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;
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

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++){
      |                   ~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32340 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32312 KB Output is correct
4 Correct 17 ms 32296 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32340 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32312 KB Output is correct
4 Correct 17 ms 32296 KB Output is correct
5 Correct 17 ms 32396 KB Output is correct
6 Correct 49 ms 32888 KB Output is correct
7 Correct 19 ms 32540 KB Output is correct
8 Correct 18 ms 32468 KB Output is correct
9 Correct 17 ms 32428 KB Output is correct
10 Correct 18 ms 32500 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32340 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32312 KB Output is correct
4 Correct 17 ms 32296 KB Output is correct
5 Correct 17 ms 32396 KB Output is correct
6 Correct 49 ms 32888 KB Output is correct
7 Correct 19 ms 32540 KB Output is correct
8 Correct 18 ms 32468 KB Output is correct
9 Correct 17 ms 32428 KB Output is correct
10 Correct 18 ms 32500 KB Output is correct
11 Correct 17 ms 32468 KB Output is correct
12 Incorrect 17 ms 32600 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 40512 KB Time limit exceeded
2 Halted 0 ms 0 KB -