oj.uz

Submission #233268

# Submission time Handle Problem Language Result Execution time Memory
233268 2020-05-20T07:57:47 Z fr_klr Planinarenje (COCI18_planinarenje) C++14
160 / 160
 11 ms 768 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3")

#include<bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()

const long long maxn = 5e3 + 10, delta = 1e9 + 7, inf = 1e9 + 420;
int n, m;

int inp(){
    int x;
    cin >> x;
    return x;
}

vector<int> adj[maxn];

bool visited[maxn];
int match[maxn];

bool dfs(int v){
    if(v == -1)
        return true;
    if(visited[v])
        return false;

    visited[v] = true;
    for(auto u : adj[v])
        if(dfs(match[u])){
            match[u] = v;
            return true;
        }
    return false;

}

void matching(){
    for(int v = 0; v < n ; v++){
        fill(visited, visited + n, 0);
        dfs(v);
    }
}

void add_edge(int u, int v){
    adj[v].push_back(u);
}

void input(){
    cin >> n >> m;
    while(m--)
        add_edge(inp() - 1, inp() - 1);
}

bool fail[maxn];
void solve(){
    fill(match, match + n, -1);
    matching();
    fill(visited, visited + n, 0);
    queue<int> q;

    for(int v = 0; v < n; v++)
        if(match[v] != -1)
            visited[match[v]] = true;
    for(int v = 0; v < n; v++)
        if(!visited[v]){
            fail[v] = true;
            q.push(v);
        }


    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : adj[v])
            if(match[u] != -1 and !fail[match[u]]){
                fail[match[u]] = true;
                q.push(match[u]);
            }
    }
}

void ansing(){
    for(int i = 0; i < n; i++)
        if(fail[i])
            cout <<"Mirko\n";
        else
            cout <<"Slavko\n";
}

inline void opting(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
}

int main(){
    opting();
    input();
    solve();
    ansing();

}

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 7 ms 640 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct

Subtask #9
16.0 / 16.0

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

Subtask #10
16.0 / 16.0

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