oj.uz

Submission #464632

# Submission time Handle Problem Language Result Execution time Memory
464632 2021-08-13T14:44:26 Z Hamed5001 Zamjena (COCI18_zamjena) C++14
70 / 70
 111 ms 9824 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 5e4+10;
int N;
string A1[mxN], A2[mxN];
bool ans = 1;

bool is_number(string& s) {
	return '0' <= s[0] && s[0] <= '9'; 
}

struct DSU {
	int N;
	vector<int> SZ, P;
	vector<set<string>> cntEq;

	DSU(int N) {
		N++;
		this->N = N;
		SZ.assign(N, 1);
		P.resize(N);
		cntEq.assign(N, set<string>());
		for (int i = 0; i < N; i++) P[i] = i;
	}

	int getParent(int a) {
		return P[a] = (P[a] == a ? a : getParent(P[a]));
	}

	bool unite(int a, int b) {
		a = getParent(a);
		b = getParent(b);

		if (a == b)
			return false;

		if (SZ[a] < SZ[b])
			swap(a, b);

		SZ[a] += SZ[b];
		P[b] = a;

		return true;
	}

};

map<string, int> ID;
int id = 1;

void solve() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A1[i];
		if (!is_number(A1[i])) {
			if (!ID[A1[i]]) {
				ID[A1[i]] = id++;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		cin >> A2[i];
		if (!is_number(A2[i])) {
			if (!ID[A2[i]]) {
				ID[A2[i]] = id++;
			}
		}
		if (is_number(A1[i]) && is_number(A2[i]) && A1[i] != A2[i])
			ans = 0;
	}

	if (!ans) return void(cout << "NE\n");

	DSU d(id);
	for (int i = 0; i < N; i++) {
		if (!is_number(A1[i]) && !is_number(A2[i]))
			d.unite(ID[A1[i]], ID[A2[i]]);
	}

	for (int i = 0; i < N && ans; ++i) {
		if (!is_number(A1[i]) && is_number(A2[i])) {
			d.cntEq[d.getParent(ID[A1[i]])].insert(A2[i]);
			if (d.cntEq[d.getParent(ID[A1[i]])].size() > 1)
				ans = 0;
		}
		if (is_number(A1[i]) && !is_number(A2[i])) {
			d.cntEq[d.getParent(ID[A2[i]])].insert(A1[i]);
			if (d.cntEq[d.getParent(ID[A2[i]])].size() > 1)
				ans = 0;
		}
	}

	cout << (ans ? "DA" : "NE") << endl;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 5 ms 3660 KB Output is correct
4 Correct 6 ms 3820 KB Output is correct
5 Correct 6 ms 3788 KB Output is correct
6 Correct 5 ms 3592 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4172 KB Output is correct
2 Correct 29 ms 5224 KB Output is correct
3 Correct 53 ms 6812 KB Output is correct
4 Correct 62 ms 7556 KB Output is correct
5 Correct 111 ms 9824 KB Output is correct
6 Correct 70 ms 6468 KB Output is correct