oj.uz

Submission #905043

# Submission time Handle Problem Language Result Execution time Memory
905043 2024-01-12T13:22:33 Z khachatur25 Marriage questions (IZhO14_marriage) C++14
10 / 100
 28 ms 6228 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 50005;

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 < (int)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);
        //int a,b;
        //cin >> 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 'int main()':
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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1624 KB Output isn't correct
2 Incorrect 1 ms 1628 KB Output isn't correct
3 Incorrect 1 ms 1628 KB Output isn't correct
4 Incorrect 1 ms 1628 KB Output isn't correct
5 Incorrect 1 ms 1628 KB Output isn't correct
6 Incorrect 1 ms 1628 KB Output isn't correct
7 Incorrect 1 ms 1628 KB Output isn't correct
8 Incorrect 1 ms 1628 KB Output isn't correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Incorrect 1 ms 1628 KB Output isn't correct
12 Correct 1 ms 1628 KB Output is correct
13 Incorrect 1 ms 1624 KB Output isn't correct
14 Incorrect 1 ms 1628 KB Output isn't correct
15 Incorrect 1 ms 1628 KB Output isn't correct
16 Incorrect 1 ms 1628 KB Output isn't correct
17 Incorrect 1 ms 1628 KB Output isn't correct
18 Incorrect 1 ms 1628 KB Output isn't correct
19 Runtime error 3 ms 2908 KB Execution killed with signal 11
20 Incorrect 1 ms 1628 KB Output isn't correct
21 Correct 1 ms 1628 KB Output is correct
22 Incorrect 1 ms 1628 KB Output isn't correct
23 Incorrect 1 ms 1628 KB Output isn't correct
24 Incorrect 1 ms 1628 KB Output isn't correct
25 Runtime error 4 ms 3160 KB Execution killed with signal 11
26 Runtime error 4 ms 3164 KB Execution killed with signal 6
27 Correct 1 ms 1436 KB Output is correct
28 Incorrect 1 ms 1628 KB Output isn't correct
29 Runtime error 5 ms 3160 KB Execution killed with signal 11
30 Runtime error 4 ms 3160 KB Execution killed with signal 11
31 Runtime error 9 ms 3932 KB Execution killed with signal 11
32 Runtime error 3 ms 3164 KB Execution killed with signal 11
33 Runtime error 3 ms 2904 KB Execution killed with signal 11
34 Runtime error 3 ms 2904 KB Execution killed with signal 11
35 Runtime error 15 ms 4892 KB Execution killed with signal 11
36 Runtime error 13 ms 4956 KB Execution killed with signal 11
37 Runtime error 10 ms 4640 KB Execution killed with signal 11
38 Runtime error 16 ms 5604 KB Execution killed with signal 11
39 Runtime error 3 ms 3160 KB Execution killed with signal 11
40 Runtime error 4 ms 3420 KB Execution killed with signal 11
41 Runtime error 6 ms 3692 KB Execution killed with signal 11
42 Runtime error 9 ms 4188 KB Execution killed with signal 6
43 Runtime error 11 ms 4188 KB Execution killed with signal 11
44 Runtime error 17 ms 5212 KB Execution killed with signal 11
45 Runtime error 11 ms 4444 KB Execution killed with signal 11
46 Runtime error 28 ms 6228 KB Execution killed with signal 6
47 Runtime error 20 ms 5464 KB Execution killed with signal 11
48 Runtime error 20 ms 5720 KB Execution killed with signal 11
49 Runtime error 24 ms 5972 KB Execution killed with signal 11
50 Runtime error 4 ms 3164 KB Execution killed with signal 11