Submission #905024

#TimeUsernameProblemLanguageResultExecution timeMemory
905024khachatur25Marriage questions (IZhO14_marriage)C++14
Compilation error
0 ms0 KiB
#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 (stderr)

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.