//Be Name Khoda, Besmellah Rahmane Rahim, In The Name Of God;
//#include<bits/stweight++.h>
#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>
#include <stdio.h>
#include <string.h>
#include<iomanip>
#include<unordered_map>
#include<unordered_set>
#include <iostream>
#include <fstream>
using namespace std;
const int N = 10000 + 5;
vector <int> adj[N];
bool mark[N];
int n, m;
int match_down[N];
int match_up[N];
bool dfs(int v)
{
mark[v] = true;
for (auto u : adj[v])
{
if (match_up[u] == -1 || (!mark[match_up[u]] && dfs(match_up[u])))
{
match_up[u] = v;
match_down[v] = u;
return true;
}
}
return false;
}
void solver()
{
bool finished = true;
int max_matching = 0;
while (finished)
{
memset(mark, 0, sizeof mark);
finished = false;
for (int i = 0; i < n; i++)
{
if (match_down[i] == -1 && !mark[i] && dfs(i))
{
finished = true;
max_matching++;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
adj[u - 1].push_back(v - 1);
}
memset(match_down, -1, sizeof match_down);
memset(match_up, -1, sizeof match_up);
solver();
for (int i = 0; i < n; i++)
{
int u = match_down[i];
if (u == -1)
{
cout << "Mirko" << endl;
}
else
{
memset(mark, 0, sizeof mark);
bool finished = false;
match_up[u] = -1;
for (int j = 0; j < n; j++)
{
if (j != i && !mark[j] && match_down[j] == -1 && dfs(j))
{
finished = true;
}
}
if (finished)
{
match_down[i] = -1;
cout << "Mirko" << endl;
}
else
{
match_up[u] = i;
cout << "Slavko" << endl;
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
4 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
640 KB |
Output is correct |
2 |
Correct |
8 ms |
640 KB |
Output is correct |
3 |
Correct |
8 ms |
640 KB |
Output is correct |
4 |
Correct |
10 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
888 KB |
Output is correct |
2 |
Correct |
281 ms |
888 KB |
Output is correct |
3 |
Correct |
241 ms |
888 KB |
Output is correct |
4 |
Correct |
276 ms |
900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
768 KB |
Output is correct |
2 |
Correct |
10 ms |
640 KB |
Output is correct |
3 |
Correct |
9 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
640 KB |
Output is correct |
2 |
Correct |
21 ms |
640 KB |
Output is correct |
3 |
Correct |
9 ms |
640 KB |
Output is correct |
4 |
Correct |
9 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
768 KB |
Output is correct |
2 |
Correct |
176 ms |
888 KB |
Output is correct |
3 |
Correct |
79 ms |
764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
768 KB |
Output is correct |
2 |
Correct |
114 ms |
768 KB |
Output is correct |
3 |
Correct |
62 ms |
760 KB |
Output is correct |
4 |
Correct |
12 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
888 KB |
Output is correct |
2 |
Correct |
69 ms |
768 KB |
Output is correct |
3 |
Correct |
97 ms |
768 KB |
Output is correct |
4 |
Correct |
30 ms |
768 KB |
Output is correct |