oj.uz

답안 #516015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516015 2022-01-20T09:55:05 Z Be_dos 결혼 문제 (IZhO14_marriage) C++17
44 / 100
 1500 ms 1292 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 > 4);

    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
44.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Runtime error 1 ms 460 KB Execution killed with signal 6
6 Runtime error 1 ms 460 KB Execution killed with signal 6
7 Correct 1 ms 312 KB Output is correct
8 Runtime error 1 ms 460 KB Execution killed with signal 6
9 Runtime error 1 ms 460 KB Execution killed with signal 6
10 Runtime error 1 ms 460 KB Execution killed with signal 6
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 316 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 6 ms 332 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 83 ms 460 KB Output is correct
26 Incorrect 11 ms 332 KB Output isn't correct
27 Correct 2 ms 204 KB Output is correct
28 Correct 1 ms 204 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 1012 KB Time limit exceeded
32 Incorrect 619 ms 332 KB Output isn't correct
33 Correct 13 ms 332 KB Output is correct
34 Correct 13 ms 364 KB Output is correct
35 Correct 116 ms 968 KB Output is correct
36 Correct 104 ms 1052 KB Output is correct
37 Execution timed out 1564 ms 900 KB Time limit exceeded
38 Incorrect 267 ms 1096 KB Output isn't correct
39 Correct 1110 ms 740 KB Output is correct
40 Correct 1373 ms 588 KB Output is correct
41 Execution timed out 1583 ms 588 KB Time limit exceeded
42 Incorrect 928 ms 772 KB Output isn't correct
43 Incorrect 1204 ms 896 KB Output isn't correct
44 Execution timed out 1571 ms 1148 KB Time limit exceeded
45 Execution timed out 1573 ms 972 KB Time limit exceeded
46 Execution timed out 1522 ms 1220 KB Time limit exceeded
47 Execution timed out 1575 ms 1216 KB Time limit exceeded
48 Execution timed out 1577 ms 1220 KB Time limit exceeded
49 Execution timed out 1564 ms 1292 KB Time limit exceeded
50 Execution timed out 1585 ms 696 KB Time limit exceeded