제출 #363508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363508		nicolaalexandra	결혼 문제 (IZhO14_marriage)	C++14	90 / 100	1569 ms	2144 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,st,dr;

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

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

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

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

    return 0;
}


void cuplaj (){

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

    } while (ok);

}



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;
    st = 1;
    for (dr=1;dr<=m;dr++){

        if (dr >= n)
            cuplaj();

        while (cnt == n && st < dr){

            if (Right[st]){
                cnt--; /// ramane nodul din stanga necuplat
                int nod = Right[st];
                Left[nod] = Right[st] = 0;
            }

            st++;

            cuplaj();
        }

        sol += st - 1;
    }

    cout<<sol;

    return 0;
}

• Subtask 1: 90 / 100