Submission #364431

#	Time	Username	Problem	Language	Result	Execution time	Memory
364431		nicolaalexandra	Marriage questions (IZhO14_marriage)	C++14	92 / 100	1576 ms	2876 KiB

marriage

#include <bits/stdc++.h>
#define DIM 30010
#define DIMBUFF 7000000
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,pos;
char buff[DIMBUFF];

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 && cnt < n);

}


int get_nr (){

    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;

    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr;

}

int main (){

    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    //cin>>m>>n>>k;
    m = get_nr(), n = get_nr(), k = get_nr();
    for (i=1;i<=k;i++){
        //cin>>x>>y;
        x = get_nr(), y = get_nr();
        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;
    }

    fprintf(fout,"%d",sol);
    //cout<<sol;

    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:79:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 92 / 100