Submission #905024

# Submission time Handle Problem Language Result Execution time Memory
905024 2024-01-12T13:04:17 Z khachatur25 Marriage questions (IZhO14_marriage) C++14
Compilation error
0 ms 0 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:1:31: warning: extra tokens at end of #include directive
    1 | #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;}
      |                               ^~~~~~~~~
marriage.cpp:1:10: fatal error: bits/stdc++.h>usin: No such file or directory
    1 | #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 terminated.