oj.uz

Submission #905031

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

const int N = 32005;

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 < 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 'bool kuhn(int, int, int)':
marriage.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     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){
      |        ~~~~^~~~

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Execution timed out 1548 ms 1116 KB Time limit exceeded
3 Execution timed out 1556 ms 1116 KB Time limit exceeded
4 Execution timed out 1526 ms 1112 KB Time limit exceeded
5 Incorrect 1 ms 1112 KB Output isn't correct
6 Incorrect 1 ms 1116 KB Output isn't correct
7 Incorrect 1 ms 1116 KB Output isn't correct
8 Incorrect 1 ms 1116 KB Output isn't correct
9 Execution timed out 1598 ms 1112 KB Time limit exceeded
10 Correct 1 ms 1112 KB Output is correct
11 Incorrect 1 ms 1116 KB Output isn't correct
12 Execution timed out 1571 ms 1116 KB Time limit exceeded
13 Incorrect 1 ms 1112 KB Output isn't correct
14 Incorrect 1 ms 1116 KB Output isn't correct
15 Execution timed out 1570 ms 1116 KB Time limit exceeded
16 Execution timed out 1530 ms 1112 KB Time limit exceeded
17 Incorrect 1 ms 1112 KB Output isn't correct
18 Incorrect 1 ms 1116 KB Output isn't correct
19 Incorrect 1 ms 1116 KB Output isn't correct
20 Incorrect 1 ms 1116 KB Output isn't correct
21 Execution timed out 1581 ms 1116 KB Time limit exceeded
22 Execution timed out 1520 ms 1112 KB Time limit exceeded
23 Incorrect 1 ms 1116 KB Output isn't correct
24 Incorrect 1 ms 1116 KB Output isn't correct
25 Incorrect 4 ms 1368 KB Output isn't correct
26 Incorrect 2 ms 1372 KB Output isn't correct
27 Execution timed out 1516 ms 1112 KB Time limit exceeded
28 Execution timed out 1548 ms 1116 KB Time limit exceeded
29 Execution timed out 1531 ms 1112 KB Time limit exceeded
30 Execution timed out 1506 ms 1112 KB Time limit exceeded
31 Incorrect 44 ms 1624 KB Output isn't correct
32 Execution timed out 1562 ms 1116 KB Time limit exceeded
33 Execution timed out 1534 ms 1112 KB Time limit exceeded
34 Execution timed out 1543 ms 1112 KB Time limit exceeded
35 Incorrect 15 ms 2388 KB Output isn't correct
36 Incorrect 10 ms 2136 KB Output isn't correct
37 Incorrect 94 ms 1948 KB Output isn't correct
38 Execution timed out 1511 ms 2648 KB Time limit exceeded
39 Execution timed out 1569 ms 1472 KB Time limit exceeded
40 Execution timed out 1539 ms 1372 KB Time limit exceeded
41 Execution timed out 1518 ms 1624 KB Time limit exceeded
42 Execution timed out 1520 ms 1624 KB Time limit exceeded
43 Execution timed out 1538 ms 1884 KB Time limit exceeded
44 Execution timed out 1508 ms 2320 KB Time limit exceeded
45 Execution timed out 1545 ms 2140 KB Time limit exceeded
46 Execution timed out 1513 ms 2648 KB Time limit exceeded
47 Execution timed out 1520 ms 2652 KB Time limit exceeded
48 Execution timed out 1524 ms 2648 KB Time limit exceeded
49 Execution timed out 1543 ms 2908 KB Time limit exceeded
50 Execution timed out 1531 ms 1372 KB Time limit exceeded