Submission #151280

#	Time	Username	Problem	Language	Result	Execution time	Memory
151280		Ruxandra985	Teoretičar (COCI18_teoreticar)	C++14	26 / 130	12077 ms	25468 KiB

teoreticar

/// o sa incerc asta dar nu cred ca e ok pt ca chiar daca ipotetic
/// intuitia mea ar fi corecta , nu sunt 100% sigura ca 12 secunde imi ajung:p
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
vector <pair <int,int> > v[200010];
int sol[500010];
int r[200001];
pair <int,int> l[200001];
bitset <200010> f;
int cuplez (int nod){
    int i,vecin;
    if (f[nod])
        return 0;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i].first;
        if (!r[vecin] && !sol[v[nod][i].second]){ /// il cuplez direct
            l[nod].first=vecin;
            l[nod].second = v[nod][i].second;
            r[vecin]=nod;
            return 1;
        }
    }
    f[nod]=1;
    /// altfel, caut alta modalitate
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i].first;
        if (!sol[v[nod][i].second] && cuplez (r[vecin])){ /// il pot cupla pe nod cu vecin
            l[nod]=make_pair(vecin , v[nod][i].second);
            r[vecin]=nod;
            return 1;
        }
    }
    return 0;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int st,dr,m,i,x,y,left,cul,ok;
    fscanf (fin,"%d%d%d",&st,&dr,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(make_pair(y,i));
    }
    left = m;
    cul = 0;
    while (left){ /// gasesti cuplaj maxim si elimini muchiile din el
        cul++;
        do{
            ok=0;
            f.reset();
            for (i=1;i<=st;i++){
                if (!l[i].first)
                    ok=(ok|cuplez(i));
            }
        }
        while (ok==1);

        for (i=1;i<=st;i++){
            if (l[i].first){
                r[l[i].first] = 0;
                left--;
                sol[l[i].second] = cul; /// scoti muchia asta
            }
            l[i] = make_pair(0,0);
        }

    }
    fprintf (fout,"%d\n",cul);
    for (i=1;i<=m;i++)
        fprintf (fout,"%d\n",sol[i]);
    return 0;
}

Compilation message (stderr)

teoreticar.cpp: In function 'int cuplez(int)':
teoreticar.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
teoreticar.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:44:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&st,&dr,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:46:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13