제출 #363492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363492		nicolaalexandra	결혼 문제 (IZhO14_marriage)	C++14	72 / 100	1592 ms	3052 KiB

marriage

#include <bits/stdc++.h>
#define DIM 30010
using namespace std;

vector <int> L[DIM];
bitset <DIM> f;
int Left[DIM],Right[DIM];
int n,m,k,i,x,y,cnt;

int cupleaza (int nod, int x, int y){
    if (f[nod])
        return 0;
    f[nod] = 1;
    for (auto vecin : L[nod]){
        if (!(vecin >= x && vecin <= y))
            continue;

        if (!Right[vecin]){
            Right[vecin] = nod;
            Left[nod] = vecin;
            cnt++;
            return 1;
        }
    }

    for (auto vecin : L[nod]){
        if (!(vecin >= x && vecin <= y))
            continue;

        if (cupleaza (Right[vecin],x,y)){
            Left[nod] = vecin;
            Right[vecin] = nod;
            return 1;
        }
    }

    return 0;
}

int cuplaj (int x, int y){

    memset (Left,0,sizeof Left);
    memset (Right,0,sizeof Right);

    int ok = 0;
    cnt = 0;

    do{
        f.reset();
        ok = 0;
        for (int i=1;i<=n;i++){
            if (!Left[i] && cupleaza (i,x,y))
                ok = 1;
        }

    } while (ok);

    return cnt;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>m>>n>>k;
    for (i=1;i<=k;i++){
        cin>>x>>y;
        L[y].push_back(x);
    }

    int sol = 0;
    for (i=n;i<=m;i++){
        int st = 1, dr = i, poz = 0;
        while (st <= dr){

            int mid = (st+dr)>>1;
            if (cuplaj(mid,i) == n){
                poz = mid;
                st = mid+1;
            } else dr = mid-1;

        }

        sol += poz;
    }

    cout<<sol;

    return 0;
}

• Subtask 1: 72 / 100