oj.uz

Submission #516017

# Submission time Handle Problem Language Result Execution time Memory
516017 2022-01-20T09:59:19 Z Be_dos Marriage questions (IZhO14_marriage) C++17
56 / 100
 1500 ms 1052 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[matched[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;
    
    assert(m > 2);

    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 matched_cnt = 0;
    for(int32_t i = 0; i < n; i++)
        matched[i] = -1;

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

        //if(rematched != -1) {
            while(right_ptr < n - 1 && matched_cnt < m) {
                right_ptr++;

                matched_cnt = 0;
                for(int32_t p = 0; p < n; p++)
                    matched[p] = -1;
                for(int32_t p = 0; p < m; p++) {
                    for(int32_t j = 0; j < m; j++)
                        vis[j] = false;
                    if(try_kuhn(p, 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
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Runtime error 1 ms 460 KB Execution killed with signal 6
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Runtime error 1 ms 460 KB Execution killed with signal 6
12 Correct 0 ms 204 KB Output is correct
13 Runtime error 1 ms 460 KB Execution killed with signal 6
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 6 ms 340 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 84 ms 408 KB Output is correct
26 Incorrect 10 ms 332 KB Output isn't correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 312 KB Output is correct
29 Incorrect 6 ms 332 KB Output isn't correct
30 Incorrect 5 ms 332 KB Output isn't correct
31 Execution timed out 1582 ms 616 KB Time limit exceeded
32 Incorrect 619 ms 452 KB Output isn't correct
33 Correct 13 ms 332 KB Output is correct
34 Correct 13 ms 332 KB Output is correct
35 Correct 118 ms 716 KB Output is correct
36 Correct 104 ms 820 KB Output is correct
37 Execution timed out 1584 ms 644 KB Time limit exceeded
38 Incorrect 258 ms 848 KB Output isn't correct
39 Correct 1106 ms 628 KB Output is correct
40 Correct 1383 ms 484 KB Output is correct
41 Execution timed out 1532 ms 460 KB Time limit exceeded
42 Incorrect 922 ms 516 KB Output isn't correct
43 Incorrect 1182 ms 636 KB Output isn't correct
44 Execution timed out 1588 ms 844 KB Time limit exceeded
45 Execution timed out 1598 ms 716 KB Time limit exceeded
46 Execution timed out 1592 ms 960 KB Time limit exceeded
47 Execution timed out 1591 ms 972 KB Time limit exceeded
48 Execution timed out 1598 ms 932 KB Time limit exceeded
49 Execution timed out 1595 ms 1052 KB Time limit exceeded
50 Execution timed out 1583 ms 648 KB Time limit exceeded