Submission #522379

#	Time	Username	Problem	Language	Result	Execution time	Memory
522379		blue	Zamjena (COCI18_zamjena)	C++17	70 / 70	85 ms	14736 KiB

zamjena

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14