oj.uz

Submission #522379

# Submission time Handle Problem Language Result Execution time Memory
522379 2022-02-04T17:36:44 Z blue Zamjena (COCI18_zamjena) C++17
70 / 70
 85 ms 14736 KB 
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

const int mx = 100'000;
using vi = vector<int>;

vi edge[mx];

void add_edge(int u, int v)
{
	edge[u].push_back(v);
	edge[v].push_back(u);
}

bool works = 1;

vi visit(mx, 0);

string rev_val[mx];

int nct = 0;

void dfs(int u)
{
	char r = rev_val[u][0];

	if('0' <= r && r <= '9') nct++;

	visit[u] = 1;
	for(int v : edge[u])
	{
		if(visit[v]) continue;
		dfs(v);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	string S[2][N];

	for(int i = 0; i < 2; i++)
		for(int j = 0; j < N; j++)
			cin >> S[i][j];

	int ct = -1;

	map<string, int> val;

	for(int i = 0; i < 2; i++)
		for(int j = 0; j < N; j++)
			val[S[i][j]] = -1;

	for(auto& p : val)
	{
		p.second = ++ct;
		rev_val[p.second] = p.first;
	}

	for(int j = 0; j < N; j++)
		add_edge(val[S[0][j]], val[S[1][j]]);


	for(int i = 0; i <= ct; i++)
	{
		nct = 0;
		if(visit[i]) continue;
		dfs(i);

		if(nct >= 2) works = 0;
	}

	if(works) cout << "DA\n";
	else cout << "NE\n";
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6220 KB Output is correct
2 Correct 4 ms 6196 KB Output is correct
3 Correct 6 ms 6596 KB Output is correct
4 Correct 6 ms 6588 KB Output is correct
5 Correct 6 ms 6604 KB Output is correct
6 Correct 6 ms 6604 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7536 KB Output is correct
2 Correct 26 ms 9016 KB Output is correct
3 Correct 49 ms 11032 KB Output is correct
4 Correct 58 ms 11956 KB Output is correct
5 Correct 85 ms 14736 KB Output is correct
6 Correct 64 ms 12280 KB Output is correct