Submission #299080

#	Time	Username	Problem	Language	Result	Execution time	Memory
299080		MladenP	Planinarenje (COCI18_planinarenje)	C++17	160 / 160	258 ms	1144 KiB

planinarenje

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define pll pair<lld,lld>
#define all(x) begin(x),end(x)
#define mid ((l+r)/2)
#define sz(x) int((x).size())
#define endl '\n'
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define INF 1000000000
#define pb push_back
using namespace std;
#define MAXN 10010
int N, M, matched[MAXN], pos[MAXN], with[MAXN];
vector<int> adj[MAXN];
bool dfs(int node) {
    pos[node] = true;
    for(auto x : adj[node]) {
        if(with[x] == 0) {
            with[x] = node;
            matched[node] = x;
            return true;
        } else if(!pos[with[x]]) {
            bool tmp = dfs(with[x]);
            if(tmp) {
                with[x] = node;
                matched[node] = x;
                return true;
            }
        }
    }
    return false;
}
int opt_matching() {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) pos[j] = 0;
        bool nadjen = 0;
        for(int j = 1; j <= N; j++) {
            if(!matched[j] && !pos[j] && dfs(j)) nadjen = true;
            if(nadjen == true) break;
        }
        if(!nadjen) return i-1;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int x, y; cin >> x >> y;
        adj[x].pb(y);
    }
    int opt = opt_matching();
    for(int i = 1; i <= N; i++) {
        if(!matched[i]) {
            cout << "Mirko\n";
            continue;
        } else {
            with[matched[i]] = 0;
            matched[i] = 0;
            for(int j = 1; j <= N; j++) pos[j] = 0;
            pos[i] = 1;
            bool nadjeno = false;
            for(int j = 1; j <= N; j++) {
                if(!pos[j] && !matched[j]) {
                    nadjeno = dfs(j);
                }
                if(nadjeno) break;
            }
            if(nadjeno) {
                cout << "Mirko\n";
            } else {
                cout << "Slavko\n";
                for(int j = 1; j <= N; j++) pos[j] = 0;
                dfs(i);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

planinarenje.cpp: In function 'int main()':
planinarenje.cpp:54:9: warning: unused variable 'opt' [-Wunused-variable]
   54 |     int opt = opt_matching();
      |         ^~~
planinarenje.cpp: In function 'int opt_matching()':
planinarenje.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

• 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