#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
vector<int> gr[N];
int matchup[N], matchdw[N], n, m;
bool ans[N], mark[N];
bool dfs(int v) {
mark[v] = 1;
for (auto u : gr[v]) {
if (matchup[u] == -1 || !mark[matchup[u]] && dfs(matchup[u])) {
matchup[u] = v;
matchdw[v] = u;
return true;
}
}
return false;
}
void getCmp(int v) {
mark[v] = 1;
for (auto u : gr[v]) {
if (!mark[matchup[u]])
getCmp(matchup[u]);
}
return;
}
int main() {
ios_base::sync_with_stdio (false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--, y--;
gr[x].push_back(y);
}
memset(matchup, -1, sizeof(matchup));
memset(matchdw, -1, sizeof(matchdw));
while (true) {
bool z = false;
for (int i = 0; i < n; i++) {
if (!mark[i] && matchdw[i] == -1) {
z |= dfs(i);
}
}
if (!z)
break;
memset(mark, 0, sizeof(mark));
}
// for (int i = 0; i < n; i++) {
// cout << matchdw[i] << " ";
// }
for (int i = 0; i < n; i++) {
if (matchdw[i] == -1) {
getCmp(i);
}
}
for (int i = 0; i < n; i++) {
if (mark[i])
cout << "Mirko\n";
else
cout << "Slavko\n";
}
return 0;
}
Compilation message
planinarenje.cpp: In function 'bool dfs(int)':
planinarenje.cpp:10:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (matchup[u] == -1 || !mark[matchup[u]] && dfs(matchup[u])) {
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
768 KB |
Output is correct |
3 |
Correct |
6 ms |
768 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
640 KB |
Output is correct |
2 |
Correct |
7 ms |
640 KB |
Output is correct |
3 |
Correct |
7 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
640 KB |
Output is correct |