oj.uz

Submission #905025

# Submission time Handle Problem Language Result Execution time Memory
905025 2024-01-12T13:04:48 Z khachatur25 Marriage questions (IZhO14_marriage) C++14
2 / 100
 1500 ms 6236 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 32005;

int n,m,k;
vector<int>g[N];

int a,b;

bool used[N];
int mt[N];

bool kuhn(int v,int L,int R){
    if(used[v])return false;
    used[v] = true;
    for(int i = 0;i < g[v].size();i++){
        int to = g[v][i];
        if(to < L)continue;
        if(to > R)break;
        if(mt[to] == -1 || kuhn(mt[to],L,R)){
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.tie(NULL);
    cin >> n >> m >> k;
    for(int i = 1;i <= k;i++){
        scanf("%d""%d",&a,&b);
        a += m;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    for(int i = 1;i <= m;i++){
        sort(g[i].begin(),g[i].end());
    }
    int ina = m, inb = n, idx = -1;
    while(ina <= inb){
        int mid = (ina + inb) >> 1;
        for(int i = 1;i <= mid;i++){
            mt[i + m] = -1;
        }
        int cnt = 0;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= m;j++){
                used[j] = false;
            }
            bool f = kuhn(i,1,mid + m);
            if(f)cnt++;
        }
        if(cnt == m){
            idx = mid;
            inb = mid - 1;
        }
        else{
            ina = mid - 1;
        }
    }
    if(idx = -1){
        cout << 0;
        return 0;
    }
    for(int i = 1;i <= n;i++){
        mt[i + m] = -1;
    }
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= m;j++){
            used[j] = false;
        }
        kuhn(i,1,idx + m);
    }
    int ans = n - idx + 1;
    for(int i = 1;i <= n;i++){
        if(mt[i + m] == -1){
            ans += n - idx + 1;
            continue;
        }
        int girl = mt[i + m];
        while(idx <= n){
            for(int j = 1;j <= m;j++){
                used[j] = false;
            }
            bool f = kuhn(girl,i + 1 + m,idx + m);
            if(f)break;
            idx++;
        }
        if(idx == n + 1)break;
        ans += n - idx + 1;
    }
    cout << ans;
}

Compilation message

marriage.cpp: In function 'bool kuhn(int, int, int)':
marriage.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0;i < g[v].size();i++){
      |                   ~~^~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:66:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |     if(idx = -1){
      |        ~~~~^~~~
marriage.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d""%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1545 ms 1116 KB Time limit exceeded
2 Execution timed out 1551 ms 1116 KB Time limit exceeded
3 Execution timed out 1561 ms 1116 KB Time limit exceeded
4 Execution timed out 1601 ms 1116 KB Time limit exceeded
5 Execution timed out 1537 ms 1116 KB Time limit exceeded
6 Execution timed out 1570 ms 1116 KB Time limit exceeded
7 Execution timed out 1554 ms 1116 KB Time limit exceeded
8 Execution timed out 1549 ms 1116 KB Time limit exceeded
9 Execution timed out 1598 ms 1116 KB Time limit exceeded
10 Correct 1 ms 1372 KB Output is correct
11 Execution timed out 1586 ms 1116 KB Time limit exceeded
12 Execution timed out 1512 ms 1116 KB Time limit exceeded
13 Execution timed out 1543 ms 1116 KB Time limit exceeded
14 Execution timed out 1552 ms 1116 KB Time limit exceeded
15 Execution timed out 1524 ms 1116 KB Time limit exceeded
16 Execution timed out 1526 ms 1116 KB Time limit exceeded
17 Execution timed out 1564 ms 1116 KB Time limit exceeded
18 Execution timed out 1530 ms 1116 KB Time limit exceeded
19 Runtime error 2 ms 2140 KB Execution killed with signal 11
20 Execution timed out 1542 ms 1368 KB Time limit exceeded
21 Execution timed out 1536 ms 1272 KB Time limit exceeded
22 Execution timed out 1535 ms 1116 KB Time limit exceeded
23 Runtime error 2 ms 2140 KB Execution killed with signal 11
24 Runtime error 2 ms 2140 KB Execution killed with signal 11
25 Runtime error 4 ms 2396 KB Execution killed with signal 11
26 Runtime error 4 ms 2140 KB Execution killed with signal 6
27 Runtime error 2 ms 2140 KB Execution killed with signal 11
28 Execution timed out 1593 ms 1212 KB Time limit exceeded
29 Runtime error 3 ms 2600 KB Execution killed with signal 11
30 Runtime error 3 ms 2140 KB Execution killed with signal 11
31 Runtime error 9 ms 3672 KB Execution killed with signal 11
32 Runtime error 3 ms 2140 KB Execution killed with signal 11
33 Runtime error 2 ms 2140 KB Execution killed with signal 11
34 Runtime error 3 ms 2140 KB Execution killed with signal 11
35 Runtime error 14 ms 4808 KB Execution killed with signal 11
36 Runtime error 13 ms 4700 KB Execution killed with signal 11
37 Runtime error 10 ms 3676 KB Execution killed with signal 11
38 Runtime error 15 ms 5468 KB Execution killed with signal 11
39 Runtime error 3 ms 2140 KB Execution killed with signal 11
40 Runtime error 4 ms 2652 KB Execution killed with signal 11
41 Runtime error 7 ms 2908 KB Execution killed with signal 11
42 Runtime error 9 ms 3676 KB Execution killed with signal 6
43 Runtime error 10 ms 3932 KB Execution killed with signal 11
44 Runtime error 17 ms 5124 KB Execution killed with signal 11
45 Runtime error 9 ms 3932 KB Execution killed with signal 11
46 Runtime error 25 ms 6228 KB Execution killed with signal 6
47 Runtime error 21 ms 5716 KB Execution killed with signal 11
48 Runtime error 18 ms 5724 KB Execution killed with signal 11
49 Runtime error 22 ms 6236 KB Execution killed with signal 11
50 Runtime error 3 ms 2140 KB Execution killed with signal 11