oj.uz

Submission #299079

# Submission time Handle Problem Language Result Execution time Memory
299079 2020-09-14T13:04:00 Z MladenP Planinarenje (COCI18_planinarenje) C++17
80 / 160
 1000 ms 2040 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) {
    //PRINT(node);
    pos[node] = true;
    for(auto x : adj[node]) {
        //PRINT(x);
        //PRINT(with[x]);
        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();
    //PRINT(opt);
    //for(int i = 1; i <= N; i++) PRINT(matched[i]);
    for(int i = 1; i <= N; i++) {
        if(!matched[i]) {
            cout << "Mirko\n";
            continue;
        } else {
            PRINT(i);
            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]) {
                    PRINT(j);
                    nadjeno = dfs(j);
                    PRINT(nadjeno);
                }
                if(nadjeno) break;
            }
            //for(int i = 1; i <= N; i++) PRINT(matched[i]);
            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:57:9: warning: unused variable 'opt' [-Wunused-variable]
   57 |     int opt = opt_matching();
      |         ^~~
planinarenje.cpp: In function 'int opt_matching()':
planinarenje.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

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 640 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 672 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 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 1828 KB Output is correct
2 Execution timed out 1002 ms 1588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 2040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 1016 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 334 ms 1016 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 760 KB Output is correct
2 Correct 104 ms 760 KB Output is correct
3 Correct 327 ms 1180 KB Output is correct
4 Correct 8 ms 768 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 1144 KB Output is correct
2 Execution timed out 1053 ms 1912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -