oj.uz

Submission #299080

# Submission time Handle Problem Language Result Execution time Memory
299080 2020-09-14T13:05:06 Z MladenP Planinarenje (COCI18_planinarenje) C++17
160 / 160
 258 ms 1144 KB 
#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

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.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 888 KB Output is correct
2 Correct 258 ms 1144 KB Output is correct
3 Correct 213 ms 888 KB Output is correct
4 Correct 257 ms 896 KB Output is correct

Subtask #6
16.0 / 16.0

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

Subtask #7
16.0 / 16.0

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

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 640 KB Output is correct
2 Correct 163 ms 804 KB Output is correct
3 Correct 57 ms 768 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 640 KB Output is correct
2 Correct 104 ms 768 KB Output is correct
3 Correct 42 ms 768 KB Output is correct
4 Correct 9 ms 800 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 760 KB Output is correct
2 Correct 49 ms 772 KB Output is correct
3 Correct 93 ms 768 KB Output is correct
4 Correct 24 ms 768 KB Output is correct