Submission #81693

#	Time	Username	Problem	Language	Result	Execution time	Memory
81693		aminra	Zamjena (COCI18_zamjena)	C++14	70 / 70	150 ms	23320 KiB

zamjena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = (int)1e5 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
string s1[MAXN], s2[MAXN];
string val[MAXN];
vector<int> G[MAXN], comp[MAXN];
int visited[MAXN], cmp = 0, n;
void dfs(int u)
{
	comp[cmp].push_back(u);
	visited[u] = 1;
	for (auto v : G[u])
		if(!visited[v])
			dfs(v);
}
unordered_map<string, int> M;
ll get(string s)
{
	if(s[0] < '0' || s[0] > '9')
		return 0;
	else
		return 1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> s1[i];
	for (int i = 0; i < n; i++)
		cin >> s2[i];
	set<string> S;
	for (int i = 0; i < n; i++)
		if(get(s1[i]) == 0)
			S.insert(s1[i]);
	for (int i = 0; i < n; i++)
		if(get(s2[i]) == 0)
			S.insert(s2[i]);
	int cnt = 0;
	for (auto u : S)
		M[u] = cnt++;
	for (int i = 0; i < n; i++)
	{
		if(get(s1[i]) == 1)
		{
			if(get(s2[i]) == 1)
			{
				if(s1[i] != s2[i])
					return cout << "NE", 0;
			}
			else
			{
				if(val[M[s2[i]]] != "" && val[M[s2[i]]] != s1[i])
					return cout << "NE", 0;
				val[M[s2[i]]] = s1[i];
			}
		}
		else
		{
			if(get(s2[i]) == 1)
			{
				if(val[M[s1[i]]] != "" && val[M[s1[i]]] != s2[i])
					return cout << "NE", 0;
				val[M[s1[i]]] = s2[i];
			}
			else
			{
				G[M[s1[i]]].push_back(M[s2[i]]);
				G[M[s2[i]]].push_back(M[s1[i]]);
			}
		}
	}
	for (int i = 0; i < cnt; i++)
		if(!visited[i])
			dfs(i), cmp++;
	for (int i = 0; i < cmp; i++)
	{
		string fir;
		for (auto u : comp[i])
			if(val[u] != "")
				fir = val[u];
		if(fir == "")
			continue;
		for (auto u : comp[i])
			if(val[u] != "" && val[u] != fir)
				return cout << "NE", 0;
	}
	cout << "DA";
}

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