#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++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
40512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
