Submission #1362673

#TimeUsernameProblemLanguageResultExecution timeMemory
1362673NikoBaoticDijamant (COI16_dijament)C++20
100 / 100
267 ms3408 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 1e3 + 10;

int n;
vector<int> dep[N];
map<string, int> c;
int vis[N];

int readUntil(string& s, int pos, char en) {
	while (pos < sz(s) and s[pos] != en) {
		pos++;
	}
	return pos;
}

bool dfs(int node, int b) {
	if (vis[node]) {
		if (vis[node] == b) return 0;
		return 1;
	}

	vis[node] = b;

	for (int x : dep[node]) {
		if (dfs(x, b)) return 1;
	}

	return 0;
}

int main() {
	FIO;
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		string l;
		while (l.empty()) getline(cin, l);
		bool valid = 1;

		int st = readUntil(l, 0, ' ');
		int ind = c[l.substr(0, st)];

		if (ind != 0) valid = 0;

		ind = i;

		int pos = st + 3;

		while (l[pos] != ';') {
			int en = readUntil(l, pos, ' ');
			string nm = l.substr(pos, en - pos);
			pos = en + 1;

			if (!c[nm]) valid = 0;
			else {
				dep[i + 1].pb(c[nm]);
			}
		}

		sort(all(dep[i + 1]));
		reverse(all(dep[i + 1]));

		memset(vis, 0, sizeof vis);

		for (int x : dep[i + 1]) {
			if (!vis[x] and dfs(x, x)) valid = 0;
		}

		if (valid) {
			c[l.substr(0, st)] = i + 1;
			cout << "ok\n";
		} else {
			cout << "greska\n";
		}
	}

	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...