Submission #237101

#	Time	Username	Problem	Language	Result	Execution time	Memory
237101		DanShaders	Zamjena (COCI18_zamjena)	C++17	14 / 70	21 ms	5632 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];
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 (pop == -2)
			pop = n;
		if (n != -2 && pop != n) {
			cout << "NE";
			exit(0);
		}
	}
	if (pop == -2)
		pop = owned[u];
	if (owned[u] != -2 && pop != owned[u]) {
		cout << "NE";
		exit(1);
	}
	return pop;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill(all(owned), -2);
	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 {
				if (owned[d1] == -2)
					owned[d1] = d2;
				if (owned[d1] != d2)
					return cout << "NE", 0;
			}
		} else {
			assert(!bv);
			if (d1 != d2) {
				return cout << "NE", 0;
			}
		}
	}
	// for (int i = 0; i < m; ++i)
	// 	for (int v : edges[i])
	// 		cout << i << "->" << v << "\n";
	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