oj.uz

Submission #81693

# Submission time Handle Problem Language Result Execution time Memory
81693 2018-10-26T08:04:03 Z aminra Zamjena (COCI18_zamjena) C++14
70 / 70
 150 ms 23320 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 18 ms 14456 KB Output is correct
3 Correct 15 ms 14488 KB Output is correct
4 Correct 15 ms 14488 KB Output is correct
5 Correct 16 ms 14548 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14748 KB Output is correct
2 Correct 15 ms 14748 KB Output is correct
3 Correct 14 ms 14748 KB Output is correct
4 Correct 13 ms 14748 KB Output is correct
5 Correct 14 ms 14748 KB Output is correct
6 Correct 14 ms 14748 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14820 KB Output is correct
2 Correct 15 ms 14820 KB Output is correct
3 Correct 18 ms 15100 KB Output is correct
4 Correct 18 ms 15228 KB Output is correct
5 Correct 19 ms 15228 KB Output is correct
6 Correct 21 ms 15228 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15936 KB Output is correct
2 Correct 54 ms 17316 KB Output is correct
3 Correct 74 ms 19356 KB Output is correct
4 Correct 96 ms 19672 KB Output is correct
5 Correct 150 ms 23320 KB Output is correct
6 Correct 103 ms 23320 KB Output is correct