oj.uz

Submission #515994

# Submission time Handle Problem Language Result Execution time Memory
515994 2022-01-20T09:21:57 Z Be_dos Marriage questions (IZhO14_marriage) C++17
18 / 100
 789 ms 262148 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

bool try_kuhn(int32_t v, bool* vis, std::vector<int32_t>* graph, int32_t* matched, int32_t left, int32_t right) {
    vis[v] = true;
    for(int32_t i = 0; i < graph[v].size(); i++)
        if(graph[v][i] >= left && graph[v][i] <= right && matched[graph[v][i]] == -1) {
            matched[graph[v][i]] = v;
            return true;
        }
    for(int32_t i = 0; i < graph[v].size(); i++)
        if(graph[v][i] >= left && graph[v][i] <= right && !vis[graph[v][i]] && try_kuhn(matched[graph[v][i]], vis, graph, matched, left, right)) {
            matched[graph[v][i]] = v;
            return true;
        }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, m, k;
    std::cin >> n >> m >> k;

    std::vector<int32_t>* graph = new std::vector<int32_t>[m];
    for(int32_t i = 0; i < k; i++) {
        int32_t src, dst;
        std::cin >> src >> dst;
        src--;
        dst--;
        //int32_t src = rand() % n, dst = rand() % m;

        graph[dst].push_back(src);
    }

    bool* vis = new bool[m];
    int32_t* matched = new int32_t[n];

    int32_t left = m - 2, right = n + 1;
    while(right - left > 1) {
        int32_t mid = (left + right) / 2;

        int32_t matched_cnt = 0;
        for(int32_t i = 0; i < n; i++)
            matched[i] = -1;
        for(int32_t i = 0; i < m; i++) {
            for(int32_t j = 0; j < m; j++)
                vis[j] = false;
            if(try_kuhn(i, vis, graph, matched, 0, mid))
                matched_cnt++;
        }
        if(matched_cnt == m)
            right = mid;
        else
            left = mid;
    }
    if(left == n) {
        std::cout << 0;
        return 0;
    }

    int32_t matched_cnt = 0;
    for(int32_t i = 0; i < n; i++)
        matched[i] = -1;
    for(int32_t i = 0; i < m; i++) {
        for(int32_t j = 0; j < m; j++)
            vis[j] = false;
        if(try_kuhn(i, vis, graph, matched, 0, right))
            matched_cnt++;
    }

    int32_t right_ptr = right;
    int32_t ans = n - right_ptr;
    for(int32_t i = 1; i < n; i++) {
        int32_t rematched = -1;
        if(matched[i - 1] != -1) {
            matched_cnt--;
            rematched = matched[i - 1];
        }

        if(rematched != -1) {
            while(right_ptr < n - 1 && matched_cnt < m) {
                right_ptr++;
                for(int32_t j = 0; j < m; j++)
                    vis[j] = false;
                if(try_kuhn(rematched, vis, graph, matched, i, right_ptr))
                    matched_cnt++;
            }
        }
        if(matched_cnt < m)
            break;

        ans += n - right_ptr;
    }
    std::cout << ans << "\n";
    return 0;
}

Compilation message

marriage.cpp: In function 'bool try_kuhn(int32_t, bool*, std::vector<int>*, int32_t*, int32_t, int32_t)':
marriage.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int32_t i = 0; i < graph[v].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~
marriage.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int32_t i = 0; i < graph[v].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Runtime error 131 ms 262148 KB Execution killed with signal 9
3 Runtime error 126 ms 262148 KB Execution killed with signal 9
4 Runtime error 123 ms 262148 KB Execution killed with signal 9
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 133 ms 262148 KB Execution killed with signal 9
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Runtime error 151 ms 262148 KB Execution killed with signal 9
15 Runtime error 125 ms 262148 KB Execution killed with signal 9
16 Runtime error 138 ms 262148 KB Execution killed with signal 9
17 Runtime error 125 ms 262148 KB Execution killed with signal 9
18 Runtime error 123 ms 262148 KB Execution killed with signal 9
19 Runtime error 270 ms 262144 KB Execution killed with signal 9
20 Runtime error 154 ms 262148 KB Execution killed with signal 9
21 Runtime error 114 ms 262148 KB Execution killed with signal 9
22 Incorrect 0 ms 204 KB Output isn't correct
23 Runtime error 177 ms 262148 KB Execution killed with signal 9
24 Runtime error 168 ms 262148 KB Execution killed with signal 9
25 Runtime error 500 ms 262148 KB Execution killed with signal 9
26 Runtime error 183 ms 262148 KB Execution killed with signal 9
27 Correct 1 ms 204 KB Output is correct
28 Incorrect 1 ms 204 KB Output isn't correct
29 Runtime error 652 ms 262148 KB Execution killed with signal 9
30 Runtime error 558 ms 262148 KB Execution killed with signal 9
31 Runtime error 428 ms 262148 KB Execution killed with signal 9
32 Runtime error 137 ms 262148 KB Execution killed with signal 9
33 Runtime error 126 ms 262148 KB Execution killed with signal 9
34 Incorrect 1 ms 332 KB Output isn't correct
35 Runtime error 789 ms 262148 KB Execution killed with signal 9
36 Runtime error 688 ms 262148 KB Execution killed with signal 9
37 Runtime error 239 ms 262148 KB Execution killed with signal 9
38 Runtime error 614 ms 262144 KB Execution killed with signal 9
39 Incorrect 2 ms 460 KB Output isn't correct
40 Runtime error 138 ms 262148 KB Execution killed with signal 9
41 Runtime error 133 ms 262148 KB Execution killed with signal 9
42 Incorrect 5 ms 460 KB Output isn't correct
43 Incorrect 8 ms 560 KB Output isn't correct
44 Incorrect 15 ms 920 KB Output isn't correct
45 Incorrect 9 ms 716 KB Output isn't correct
46 Incorrect 21 ms 1868 KB Output isn't correct
47 Incorrect 25 ms 972 KB Output isn't correct
48 Incorrect 16 ms 976 KB Output isn't correct
49 Incorrect 21 ms 1992 KB Output isn't correct
50 Incorrect 3 ms 588 KB Output isn't correct