oj.uz

Submission #94769

# Submission time Handle Problem Language Result Execution time Memory
94769 2019-01-23T15:29:01 Z teomrn Planinarenje (COCI18_planinarenje) C++14
160 / 160
 37 ms 1016 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 632 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1016 KB Output is correct
2 Correct 13 ms 1016 KB Output is correct
3 Correct 12 ms 1016 KB Output is correct
4 Correct 13 ms 1016 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 764 KB Output is correct
2 Correct 20 ms 796 KB Output is correct
3 Correct 11 ms 760 KB Output is correct

Subtask #7
16.0 / 16.0

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

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 14 ms 988 KB Output is correct
3 Correct 9 ms 888 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Correct 10 ms 888 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 37 ms 888 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 888 KB Output is correct
2 Correct 8 ms 760 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 8 ms 760 KB Output is correct