/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, match[N];
vector<int> adj[N];
bitset<N> mark;
bool dfs1(int u) {
mark[u] = true;
for (auto v: adj[u])
if (!~match[v] || (!mark[match[v]] && dfs1(match[v]))) {
match[match[v] = u] = v;
return true;
}
return false;
}
void dfs2(int u) {
mark[u] = true;
for (auto v: adj[u])
if (~match[v] && !mark[match[v]])
dfs2(match[v]);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v += n - 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(match, -1, sizeof match);
for (int ok = 1; ok; mark.reset())
for (int u = ok = 0; u < n; u++)
if (!~match[u] && !mark[u])
ok |= dfs1(u);
for (int u = 0; u < n; u++)
if (!~match[u] && !mark[u])
dfs2(u);
for (int u = 0; u < n; u++)
cout << (mark[u]? "Mirko\n": "Slavko\n");
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
608 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
556 KB |
Output is correct |
2 |
Correct |
3 ms |
540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
540 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
640 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
4 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
948 KB |
Output is correct |
2 |
Correct |
7 ms |
996 KB |
Output is correct |
3 |
Correct |
13 ms |
896 KB |
Output is correct |
4 |
Correct |
9 ms |
996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
3 |
Correct |
7 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
4 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
8 ms |
896 KB |
Output is correct |
3 |
Correct |
7 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
896 KB |
Output is correct |
3 |
Correct |
7 ms |
768 KB |
Output is correct |
4 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
768 KB |
Output is correct |
2 |
Correct |
4 ms |
768 KB |
Output is correct |
3 |
Correct |
8 ms |
896 KB |
Output is correct |
4 |
Correct |
7 ms |
832 KB |
Output is correct |