Submission #94769

#	Time	Username	Problem	Language	Result	Execution time	Memory
94769		teomrn	Planinarenje (COCI18_planinarenje)	C++14	160 / 160	37 ms	1016 KiB

planinarenje

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 5010;
int cuplat[2 * NMAX];
vector <int> adia[2 * NMAX];
int viz[2 * NMAX];

bool cuplaj(int nod)
{
	if (viz[nod])
		return 0;
	viz[nod] = 1;
	
	for (auto i : adia[nod]) {
		if (!cuplat[i]) {
			cuplat[i] = nod;
			cuplat[nod] = i;
			return 1;
		}
	}
	for (auto i : adia[nod]) {
		if (cuplaj(cuplat[i])) {
			cuplat[i] = nod;
			cuplat[nod] = i;
			return 1;
		}
	}
	return 0;
}

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

	int n, m, a, b;
	cin >> n >> m;

	while (m--) {
		cin >> a >> b;
		adia[a].push_back(b + n);
		adia[b + n].push_back(a);
	}

	bool ok = 1;
	while (ok) {
		ok = 0;
		memset(viz, 0, sizeof viz);
		for (int i = 1; i <= n; i++)
			if (!cuplat[i] && cuplaj(i))
				ok = 1;
	}

	for (int i = 1; i <= n; i++) {
		memset(viz, 0, sizeof viz);
		if (!cuplat[i] || cuplaj(cuplat[i])) {
			cuplat[i] = 0;
			cout << "Mirko\n";
		}
		else
			cout << "Slavko\n";
	}

	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16