Submission #600676

#	Time	Username	Problem	Language	Result	Execution time	Memory
600676		starchan	Zamjena (COCI18_zamjena)	C++17	56 / 70	66 ms	12080 KiB

zamjena

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
map<string, int> comp;
int cnt;
bool works;
bool num(string ok)
{
	return (ok[0] >= '1' && ok[0] <= '9');
}
int assign(string ok)
{
	if(comp[ok])
		return comp[ok];
	else
		return comp[ok] = ++cnt;
}
vector<int> pa(MX, -1);
vector<int> val(MX, 0);
int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}
void merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u==v)
		return;
	if(val[u] && val[v] && val[u] != val[v])
		works = 0;
	val[u] = max(val[u], val[v]);
	val[v] = max(val[u], val[v]);
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v] += pa[u];
	pa[u] = v;
	return;
}
signed main()
{
	fast();
	cnt = 0;
	int n;
	cin >> n;	
	works = 1;
	vector<string> a(n+1);
	vector<string> b(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> b[i];
	for(int i = 1; i <= n && works; i++)
	{
		if(num(a[i]) && num(b[i]))
		{
			if(a[i] == b[i])
				continue;
			else
				works = 0;
		}
		if(num(b[i]))
			swap(a[i], b[i]);
		if(num(a[i]))
		{
			int uwu = val[leader(assign(b[i]))];
			if(uwu && uwu != stoi(a[i]))
				works = 0;
			else
				val[leader(assign(b[i]))] = stoi(a[i]);
			continue;
		}
		merge(assign(a[i]), assign(b[i]));
	}
	if(works)
		cout << "DA";
	else
		cout << "NE";
	return 0;
}	

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