This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int n, m;
int mat[maxn];
vector<int> adj[maxn];
bitset<maxn> mark, fmat, ans;
bool dfs(int v){
if (mark[v]) return false;
mark[v] = true;
for (auto u:adj[v])
if (mat[u] == -1 || dfs(mat[u])){
mat[u] = v;
return true;
}
return false;
}
void dfs2(int v){
if (mark[v]) return;
mark[v] = true;
for (auto u:adj[v])
if (mat[u] != -1){
ans[mat[u]] = true;
dfs2(mat[u]);
}
return;
}
int main(){
memset(mat, -1, sizeof(mat));
cin >> n >> m;
for (int i = 0, v, u; i < m; i++){
cin >> v >> u; v--, u--;
adj[v].push_back(u);
}
bool find = true;
while (find){
find = false;
mark.reset();
for (int i = 0; i < n; i++)
if (!fmat[i] && dfs(i))
fmat[i] = find = true;
}
mark.reset();
for (int i = 0; i < n; i++)
if (!fmat[i])
dfs2(i);
for (int i = 0; i < n; i++){
if (!fmat[i] || ans[i])
cout << "Mirko\n";
else
cout << "Slavko\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |