Submission #237099

#	Time	Username	Problem	Language	Result	Execution time	Memory
237099		DanShaders	Zamjena (COCI18_zamjena)	C++17	14 / 70	35 ms	7424 KiB

zamjena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

const int MAX_N = 5e4 + 10;

string a[MAX_N], b[MAX_N];
map<string, int> varId;

vector<int> edges[MAX_N];
vector<int> owned[MAX_N];
char used[MAX_N];

int m = 0;

int getVarId(string s) {
	if (!varId.count(s))
		varId[s] = m++;
	return varId[s];
}

int dfs(int u) {
	if (used[u])
		return -2;
	used[u] = 1;
	int pop = -2;
	for (int v : edges[u]) {
		int n = dfs(v);
		if (n == -1)
			return -1;
		if (pop == -2)
			pop = n;
		if (pop != n)
			return -1;
	}
	for (int v : owned[u]) {
		if (pop == -2)
			pop = v;
		if (pop != v)
			return -1;
	}
	return pop;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < n; ++i)
		cin >> b[i];
	for (int i = 0; i < n; ++i) {
		bool av = 0, bv = 0;
		int d1 = -1, d2 = -1;
		if (isdigit(a[i][0])) {
			d1 = stoi(a[i]);
		} else {
			av = 1;
			d1 = getVarId(a[i]);
		}
		if (isdigit(b[i][0])) {
			d2 = stoi(b[i]);
		} else {
			bv = 1;
			d2 = getVarId(b[i]);
		}

		if (av < bv)
			swap(av, bv), swap(d1, d2);
		// cout << av << " " << d1 << " " << bv << " " << d2 << endl;
		if (av == 1) {
			if (bv == 1) {
				edges[d1].push_back(d2);
				edges[d2].push_back(d1);
			} else {
				owned[d1].push_back(d2);
			}
		} else {
			if (d1 != d2) {
				return cout << "NE", 0;
			}
		}
	}
	for (int i = 0; i < m; ++i) {
		if (dfs(i) == -1)
			return cout << "NE", 0;
	}
	cout << "DA";
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14