oj.uz

Submission #237097

# Submission time Handle Problem Language Result Execution time Memory
237097 2020-06-04T15:33:25 Z DanShaders Zamjena (COCI18_zamjena) C++17
14 / 70
 36 ms 7544 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];
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 (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);
		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) {
				cout << "NE\n";
				return 0;
			}
		}
	}
	for (int i = 0; i < m; ++i) {
		if (dfs(i) == -1)
			return cout << "NE\n", 0;
	}
	cout << "DA";
	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5760 KB Output is correct
2 Correct 8 ms 5760 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Incorrect 8 ms 5888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6656 KB Output is correct
2 Incorrect 36 ms 7544 KB Output isn't correct
3 Halted 0 ms 0 KB -