Submission #151566

#	Time	Username	Problem	Language	Result	Execution time	Memory
151566		Ruxandra985	Teoretičar (COCI18_teoreticar)	C++14	13 / 130	12104 ms	91932 KiB

teoreticar

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
vector <pair <int,int> > v[400010];
vector <pair <pair <int,int>,int> > mc;
int sol[500010];
int g[400010];
int prv[400010];
int f[500010];
int m , st , dr;
void findd (int nod,int pus,vector <pair <pair <int,int>,int> > other[2]){
    int vecin,mch,i;
    //if (nod == 3)
      //  printf ("a");
    while (1){
        for (i = prv[nod] ; i <v[nod].size();i++){
            prv[nod] = i;
            vecin = v[nod][prv[nod]].first;
            mch = v[nod][prv[nod]].second;
            //printf ("%d\n",mch)
            if (!f[mch]){
                f[mch] = 1;
                g[nod]--;
                g[vecin]--;
                other[pus].push_back(make_pair(make_pair(nod,vecin),mch));
                prv[nod]++;
                pus = 1 - pus;
                nod = vecin;
                break;
            }
            prv[nod]++;
        }
        if ( i == v[nod].size() )
            break;
    }
}
void pune (vector <pair <pair <int,int>,int> > mc , int &cul){
    /// pt chestia cu 2^x , o sa imparti muchiile mereu in 2
    int i,x,y,idx,gmax;
    /// verifici daca setul tau e independent
    gmax = 0;
    for (i=0;i<mc.size();i++){
        x = mc[i].first.first;
        y = mc[i].first.second;
        prv[x] = prv[y] = 0;
        //printf ("%d %d\n",x,y);
        idx = mc[i].second;
        f[idx] = 0;

        v[x].push_back(make_pair(y,idx));
        v[y].push_back(make_pair(x,idx));
        g[y]++; g[x]++;
        gmax = max (gmax , g[x]);
        gmax = max (gmax , g[y]);
    }
    //printf ("\n\n");
    if ( gmax < 2 ) { /// e independent , pui cul peste tot
        if (!mc.empty())
            cul++;
        for (i=0;i<mc.size();i++){
            idx = mc[i].second;
            g[mc[i].first.first] = g[mc[i].first.second] = 0;
            v[mc[i].first.first].clear();
            v[mc[i].first.second].clear();
            sol[idx] = cul;
        }
        return;
    }
    vector <pair <pair <int,int>,int> > other[2];
    /// vrei sa imparti muchiile in doua seturi astfel incat niciuna din primul set
    /// sa nu aiba aceeasi culoare cu una din al doilea set
    /// iei pur si simplu drumuri maximale si pui muchiile alternant,cum faceam
    /// si la euler
    /// trebuie sa am grija ca mereu sa pun ceva in ambele other uri

    for (i=1;i<=st+dr;i++){
        if (g[i]&1)
            findd(i,0,other);
    }

    for (i=1;i<=st+dr;i++){
        while (g[i]){
            findd (i,0,other);
        }
        v[i].clear();
    }
    pune(other[0],cul);
    pune(other[1],cul);

}
char buff[7000000];
int poz = 0;
int getnr(){
    int nr = 0;
    while ('0' > buff[poz] || buff[poz] > '9')
        poz++;
    while ('0'<=buff[poz] && buff[poz]<='9'){
        nr = nr * 10 + buff[poz] - '0';
        poz++;
    }
    return nr;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i,x,y,cul=0;
    fread (buff,1,7000000,fin);
    st = getnr();
    dr = getnr();
    m = getnr();
    for (i=1;i<=m;i++){
        x = getnr();
        y = getnr();
        y+=st;
        mc.push_back(make_pair(make_pair(x,y),i));

    }
    cul = 0;
    pune(mc,cul);

    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 'void findd(int, int, std::vector<std::pair<std::pair<int, int>, int> >*)':
teoreticar.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = prv[nod] ; i <v[nod].size();i++){
                             ~~^~~~~~~~~~~~~~
teoreticar.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( i == v[nod].size() )
              ~~^~~~~~~~~~~~~~~~
teoreticar.cpp: In function 'void pune(std::vector<std::pair<std::pair<int, int>, int> >, int&)':
teoreticar.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<mc.size();i++){
              ~^~~~~~~~~~
teoreticar.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<mc.size();i++){
                  ~^~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:111:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,7000000,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 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