oj.uz

Submission #905036

# Submission time Handle Problem Language Result Execution time Memory
905036 2024-01-12T13:13:44 Z khachatur25 Marriage questions (IZhO14_marriage) C++14
2 / 100
 1500 ms 3344 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 < 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 1628 KB Output isn't correct
2 Execution timed out 1553 ms 1628 KB Time limit exceeded
3 Execution timed out 1518 ms 1628 KB Time limit exceeded
4 Execution timed out 1544 ms 1628 KB Time limit exceeded
5 Incorrect 1 ms 1624 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 Execution timed out 1574 ms 1628 KB Time limit exceeded
10 Correct 1 ms 1628 KB Output is correct
11 Incorrect 1 ms 1628 KB Output isn't correct
12 Execution timed out 1584 ms 1628 KB Time limit exceeded
13 Incorrect 1 ms 1624 KB Output isn't correct
14 Incorrect 1 ms 1624 KB Output isn't correct
15 Execution timed out 1562 ms 1628 KB Time limit exceeded
16 Execution timed out 1532 ms 1628 KB Time limit exceeded
17 Incorrect 1 ms 1624 KB Output isn't correct
18 Incorrect 1 ms 1628 KB Output isn't correct
19 Incorrect 1 ms 1628 KB Output isn't correct
20 Incorrect 1 ms 1628 KB Output isn't correct
21 Execution timed out 1514 ms 1624 KB Time limit exceeded
22 Execution timed out 1577 ms 1624 KB Time limit exceeded
23 Incorrect 1 ms 1624 KB Output isn't correct
24 Incorrect 2 ms 1628 KB Output isn't correct
25 Incorrect 4 ms 1628 KB Output isn't correct
26 Incorrect 2 ms 1624 KB Output isn't correct
27 Execution timed out 1530 ms 1624 KB Time limit exceeded
28 Execution timed out 1511 ms 1624 KB Time limit exceeded
29 Execution timed out 1518 ms 1624 KB Time limit exceeded
30 Execution timed out 1528 ms 1628 KB Time limit exceeded
31 Incorrect 49 ms 2468 KB Output isn't correct
32 Execution timed out 1530 ms 1624 KB Time limit exceeded
33 Execution timed out 1547 ms 1628 KB Time limit exceeded
34 Execution timed out 1525 ms 1624 KB Time limit exceeded
35 Incorrect 12 ms 2648 KB Output isn't correct
36 Incorrect 10 ms 2648 KB Output isn't correct
37 Incorrect 92 ms 2140 KB Output isn't correct
38 Execution timed out 1503 ms 2904 KB Time limit exceeded
39 Execution timed out 1523 ms 1880 KB Time limit exceeded
40 Execution timed out 1547 ms 1884 KB Time limit exceeded
41 Execution timed out 1529 ms 1880 KB Time limit exceeded
42 Execution timed out 1559 ms 2140 KB Time limit exceeded
43 Execution timed out 1538 ms 2396 KB Time limit exceeded
44 Execution timed out 1543 ms 2808 KB Time limit exceeded
45 Execution timed out 1539 ms 2396 KB Time limit exceeded
46 Execution timed out 1534 ms 3164 KB Time limit exceeded
47 Execution timed out 1565 ms 3164 KB Time limit exceeded
48 Execution timed out 1554 ms 2908 KB Time limit exceeded
49 Execution timed out 1560 ms 3344 KB Time limit exceeded
50 Execution timed out 1543 ms 1884 KB Time limit exceeded