제출 #233268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233268		fr_klr	Planinarenje (COCI18_planinarenje)	C++14	160 / 160	11 ms	768 KiB

planinarenje

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16