oj.uz

Submission #600676

# Submission time Handle Problem Language Result Execution time Memory
600676 2022-07-21T06:55:33 Z starchan Zamjena (COCI18_zamjena) C++17
56 / 70
 66 ms 12080 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5028 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5024 KB Output is correct
4 Incorrect 2 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6100 KB Output is correct
2 Correct 28 ms 7416 KB Output is correct
3 Correct 33 ms 8816 KB Output is correct
4 Correct 29 ms 9428 KB Output is correct
5 Correct 66 ms 12080 KB Output is correct
6 Correct 52 ms 10076 KB Output is correct