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;
vector <int> graf[10005];
vector <int> rgraf[10005];
int mt[10005];
bool used[10005];
int ime[10005];
int pime[10005];
int pmt[100005];
bool bp(int v) {
if (used[v]) return false;
used[v] = true;
for (auto c : graf[v]) {
if(!mt[c] || bp(mt[c])) {
mt[c] = v;
ime[v] = c;
return true;
}
}
return false;
}
bool bio[10005];
int main()
{
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++){
int a, b;
cin >> a >> b;
graf[a].push_back(b);
rgraf[b].push_back(a);
}
int mxm = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++) used[j] = 0;
mxm += bp(i);
}
for(int i=1; i<=n; i++){
bio[mt[i]] = 1;
pime[i] = ime[i];
pmt[i] = mt[i];
}
for(int i=1; i<=n; i++){
if(!bio[i]){
cout << "Mirko\n";
continue;
}
int tren = mxm-1;
int koji = pime[i];
for(int j=1; j<=n; j++){
mt[j] = pmt[j];
ime[j] = pime[j];
}
mt[koji] = 0;
for(auto j : rgraf[koji]){
if(j == i) continue;
//cout << "pokusam " << j << endl;
if(ime[j]) continue;
for(int k=1; k<=n; k++) used[k] = 0;
used[i] = 1;
tren += bp(j);
}
//cout << mxm << " " << tren << endl;
if(tren-mxm) cout << "Slavko\n";
else cout << "Mirko\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... |