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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>
const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
using namespace __gnu_pbds;
bool valid(int x, int y, int n, int m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937 rng(1999999973);
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int N = 5050;
int nxt[N], mt[N], n, m;
bool vis[N];
vector<int> g[N], gr[N];
bool kuhn(int v) {
if (vis[v])
return false;
vis[v] = true;
for (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (mt[to] == -1 || kuhn(mt[to])) {
mt[to] = v;
nxt[v] = to;
return true;
}
}
return false;
}
bool good(int v) {
if (vis[v])
return true;
vis[v] = true;
for (int i = 0; i < gr[v].size(); i++) {
int to = gr[v][i];
if (nxt[to] == -1 || !good(nxt[to]))
return false;
}
return true;
}
signed main() {
fast_io;
cin >> n >> m;
fill(mt, mt + n, -1);
fill(nxt, nxt + n, -1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].pb(v);
gr[v].pb(u);
}
for (int i = 0; i < n; i++) {
fill(vis, vis + n, false);
kuhn(i);
}
for (int i = 0; i < n; i++) {
fill(vis, vis + n, false);
if (nxt[i] == -1 || !good(nxt[i]))
cout << "Mirko" << endl;
else
cout << "Slavko" << endl;
}
return 0;
}
Compilation message (stderr)
planinarenje.cpp: In function 'bool kuhn(int)':
planinarenje.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++) {
~~^~~~~~~~~~~~~
planinarenje.cpp: In function 'bool good(int)':
planinarenje.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < gr[v].size(); i++) {
~~^~~~~~~~~~~~~~
# | 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... |