oj.uz

Submission #237102

# Submission time Handle Problem Language Result Execution time Memory
237102 2020-06-04T16:07:35 Z DanShaders Zamjena (COCI18_zamjena) C++17
70 / 70
 120 ms 10360 KB 
#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(0);
	}
	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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4864 KB Output is correct
2 Correct 7 ms 4864 KB Output is correct
3 Correct 7 ms 4864 KB Output is correct
4 Correct 7 ms 4864 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4864 KB Output is correct
2 Correct 7 ms 4864 KB Output is correct
3 Correct 7 ms 4864 KB Output is correct
4 Correct 7 ms 4864 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4864 KB Output is correct
2 Correct 8 ms 4864 KB Output is correct
3 Correct 7 ms 4864 KB Output is correct
4 Correct 7 ms 4864 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct
6 Correct 7 ms 4864 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4864 KB Output is correct
3 Correct 11 ms 5120 KB Output is correct
4 Correct 11 ms 5248 KB Output is correct
5 Correct 12 ms 5120 KB Output is correct
6 Correct 11 ms 4992 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5632 KB Output is correct
2 Correct 36 ms 6272 KB Output is correct
3 Correct 63 ms 7800 KB Output is correct
4 Correct 68 ms 8064 KB Output is correct
5 Correct 120 ms 10360 KB Output is correct
6 Correct 82 ms 7800 KB Output is correct