oj.uz

Submission #436992

# Submission time Handle Problem Language Result Execution time Memory
436992 2021-06-25T14:00:33 Z mostafa Planinarenje (COCI18_planinarenje) C++14
160 / 160
 11 ms 672 KB 
// 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=5e3+10;
vector<int> adj[MX];
bool match1[MX];
int match2[MX];
bool mrk[MX];

bool dfs(int v)
{
    mrk[v]=1;
    if(!adj[v].size()) return 0;
    for(int u:adj[v]){
        if(!match2[u]){
            match1[v]=1;
            match2[u]=v;
            return 1;
        }
    }
    for(int u:adj[v]){
        if(!mrk[match2[u]]&&dfs(match2[u])){
            match1[v]=1;
            match2[u]=v;
            return 1;
        }
    }
    return 0;
}

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]==0){
            fill(mrk,mrk+n+2,0);
            solve(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(ans[i]) cout<<"Mirko"<<endl;
        else cout<<"Slavko"<<endl;
    }
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 388 KB Output is correct
4 Correct 2 ms 460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 588 KB Output is correct
2 Correct 11 ms 588 KB Output is correct
3 Correct 10 ms 672 KB Output is correct
4 Correct 11 ms 588 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 11 ms 588 KB Output is correct
3 Correct 7 ms 572 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 8 ms 628 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 548 KB Output is correct
2 Correct 6 ms 460 KB Output is correct
3 Correct 8 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct