oj.uz

Submission #905040

# Submission time Handle Problem Language Result Execution time Memory
905040 2024-01-12T13:19:59 Z khachatur25 Marriage questions (IZhO14_marriage) C++14
14 / 100
 185 ms 3164 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 50005;

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

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:66:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |     if(idx = -1){
      |        ~~~~^~~~

Subtask #1
14.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 1532 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 1624 KB Output isn't correct
7 Incorrect 1 ms 1628 KB Output isn't correct
8 Incorrect 1 ms 1880 KB Output isn't correct
9 Correct 1 ms 1880 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Incorrect 1 ms 1628 KB Output isn't correct
12 Correct 2 ms 1628 KB Output is correct
13 Incorrect 1 ms 1628 KB Output isn't correct
14 Incorrect 2 ms 1624 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 2 ms 1628 KB Output isn't correct
18 Incorrect 1 ms 1628 KB Output isn't correct
19 Incorrect 2 ms 1628 KB Output isn't correct
20 Incorrect 2 ms 1628 KB Output isn't correct
21 Correct 2 ms 1624 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 Incorrect 4 ms 1824 KB Output isn't correct
26 Incorrect 2 ms 1628 KB Output isn't correct
27 Correct 1 ms 1560 KB Output is correct
28 Incorrect 2 ms 1628 KB Output isn't correct
29 Incorrect 2 ms 1628 KB Output isn't correct
30 Incorrect 2 ms 1628 KB Output isn't correct
31 Incorrect 43 ms 2236 KB Output isn't correct
32 Incorrect 4 ms 1628 KB Output isn't correct
33 Correct 1 ms 1628 KB Output is correct
34 Incorrect 10 ms 1628 KB Output isn't correct
35 Incorrect 13 ms 2616 KB Output isn't correct
36 Incorrect 11 ms 2652 KB Output isn't correct
37 Incorrect 92 ms 2372 KB Output isn't correct
38 Incorrect 14 ms 2920 KB Output isn't correct
39 Incorrect 181 ms 1884 KB Output isn't correct
40 Correct 4 ms 1884 KB Output is correct
41 Incorrect 7 ms 1884 KB Output isn't correct
42 Incorrect 6 ms 2140 KB Output isn't correct
43 Incorrect 11 ms 2396 KB Output isn't correct
44 Incorrect 15 ms 2652 KB Output isn't correct
45 Incorrect 8 ms 2356 KB Output isn't correct
46 Incorrect 34 ms 3164 KB Output isn't correct
47 Incorrect 20 ms 2904 KB Output isn't correct
48 Incorrect 15 ms 3164 KB Output isn't correct
49 Incorrect 38 ms 3160 KB Output isn't correct
50 Incorrect 185 ms 2300 KB Output isn't correct