Submission #1297178

#TimeUsernameProblemLanguageResultExecution timeMemory
1297178mdobricDijamant (COI16_dijament)C++20
27 / 100
245 ms696 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int n;
map <string, int> m;
int greska, bio[maxn];
vector <int> parent[maxn], v;
int ostavi[maxn];

void dfs (int x, int poc){
	if (parent[x].size() == 0 and bio[x] != -1){
		greska = 1;
		return;
	}
	else if (parent[x].size() == 0){
		bio[x] = poc;
		return;
	}
	if (bio[x] != -1 and x == poc){
		ostavi[x] = 1;
		return;
	}
	else if (bio[x] != -1){
		ostavi[bio[x]] = 1;
		return;
	}
	bio[x] = poc;
	for (int i = 0; i < parent[x].size(); i++){
		int y = parent[x][i];
		dfs(y, poc);
	}
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	int br = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= br; j++) bio[j] = -1, ostavi[j] = 0;
		v.clear();
		greska = 0;
		string novi, s;
		cin >> novi;
		if (m[novi] != 0){
			greska = 1; 
		}
		cin >> s;
		string roditelj;
		cin >> roditelj;
		while (roditelj != ";"){
			v.push_back(m[roditelj]);
			if (m[roditelj] == 0){
				greska = 1;
			}
			else{
				if (parent[m[roditelj]].size() != 0) dfs(m[roditelj], m[roditelj]);				
			}
			cin >> roditelj;
		}
		//cout << bio[1] << " " << bio[2] << " " << bio[3] << endl;
		//cout << greska << endl;
		if (greska == 1) cout << "greska" << endl;
		else{
			cout << "ok" << "\n";
			m[novi] = br;
			//cout << br << " : ";
			for (int j = 0; j < v.size(); j++){
				if (ostavi[v[j]] == 0 and (parent[v[j]].size() > 0 or bio[v[j]] == -1)){
					//cout << v[j] << " ";
					parent[br].push_back(v[j]);
				}
			}
			br++;
			//cout << endl;
		}
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...