Submission #363502

#	Time	Username	Problem	Language	Result	Execution time	Memory
363502		nicolaalexandra	Marriage questions (IZhO14_marriage)	C++14	50 / 100	1594 ms	3116 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 add (){

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

    } while (ok);

}

void delete_ (){

    if (!Right[st]) /// nodul asta nu face parte din cuplaj
        return;

    cnt--; /// ramane nodul din stanga necuplat
    int nod = Right[st];
    Left[nod] = Right[st] = 0;

    st++;
    cupleaza(nod);
}

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);
    }

    /*for (i=1;i<=n;i++){
        sort (L[i].begin(),L[i].end());
        reverse (L[i].begin(),L[i].end());
    }*/

    int sol = 0;
    st = 1;
    for (dr=1;dr<=m;dr++){
        /// adaug nodul asta
        add ();

        while (cnt == n && st <= i){
            delete_();
            if (cnt < n){
                st--;
                add(); /// il adaug la loc
                break;
            }
        }

        if (cnt == n)
            sol += st;
    }

    cout<<sol;

    return 0;
}

• Subtask 1: 50 / 100