# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
436986 | mostafa | Planinarenje (COCI18_planinarenje) | C++14 | 6 ms | 3276 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// in the name of GOD++
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mpp make_pair
#define pb push_back
#define F first
#define S second
//#pragma GCC optimize("O2")
const int MX=5e4+10;
vector<int> adj[MX];
bool match1[MX];
int match2[MX];
bool mrk[MX];
bool dfs(int v)
{
mrk[v]=1;
for(int u:adj[v]){
if(!match2[u]){
match1[v]=u;
match2[u]=v;
return 1;
}
}
for(int u:adj[v]){
if(!mrk[match2[u]]&&dfs(match2[u])){
match1[v]=u;
match2[u]=v;
return 1;
}
}
}
bool ans[MX];
void solve(int v)
{
mrk[v]=1;
ans[v]=1;
for(int u:adj[v]){
if(!mrk[match2[u]]) solve(match2[u]);
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u;
adj[v].pb(u);
}
int fnd=1;
while(fnd){
fnd=0;
fill(mrk,mrk+n+2,0);
for(int i=1;i<=n;i++){
if((!mrk[i])&&(!match1[i])&&dfs(i)){
fnd=1;
}
}
}
fill(mrk,mrk+n+2,0);
for(int i=1;i<=n;i++){
if(!match1[i]) solve(i);
}
for(int i=1;i<=n;i++){
if(ans[i]) cout<<"Mirko"<<endl;
else cout<<"Slavko"<<endl;
}
return 0;
}
Compilation message (stderr)
# | 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... |