Submission #167698

#	Time	Username	Problem	Language	Result	Execution time	Memory
167698		rzbt	Teoretičar (COCI18_teoreticar)	C++14	52 / 130	2435 ms	84456 KiB

teoreticar

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

int l,r,m;
vector<pair<int,int> > niz[2*MAXN];
pair<int,int> grane[5*MAXN];
int boje[5*MAXN];
vector<int> resip,tcvor,levi,desni;
int bboja=0,maxd;
bool aktivan[2*MAXN],obidjen[10*MAXN];
int pocs[2*MAXN];
int temp[5*MAXN],pokom[5*MAXN],gde[5*MAXN];
stack<pair<int,int> > s;
void ojler(int t,int grana,int znak,int dub){
    //if(t==24)printf(" euler   %d %d   %d\n",t,dub,grana);
    //printf("    %d %d  %d %d\n",t,grana,znak,dub);
    s.push(mp(t,grana));
    obidjen[grana]=true;
    while(!s.empty()){
        t=s.top().first,grana=s.top().second;
        obidjen[grana]=true;
        if(niz[t].empty()){
            //printf("   %d %d   %d\n",t,grana,znak);
            boje[grana]|=(znak<<dub);
            if(znak)desni.pb(grana);
            else levi.pb(grana);
            s.pop();
            znak=1-znak;
            continue;
        }
        if(obidjen[niz[t].back().second]){
            niz[t].pop_back();
            continue;
        }
        s.push(niz[t].back());
        niz[t].pop_back();
        znak=1-znak;

    }





}


void resi(int dub,int lg,int dg){
    if(dub>=maxd)return;
    levi.clear();
    desni.clear();

    for(int f=lg;f<=dg;f++){
        int x=pokom[f];
        obidjen[x]=false;
        int a=grane[x].F,b=grane[x].S;
        if(!aktivan[a]){
            aktivan[a]=true;
            niz[a].clear();
            tcvor.pb(a);
        }
        if(!aktivan[b]){
            aktivan[b]=true;
            niz[b].clear();
            tcvor.pb(b);
        }
        niz[a].pb(mp(b,x));
        niz[b].pb(mp(a,x));

    }
    niz[l+r+1].clear();
    niz[0].clear();
    int nfus=0;
    for(auto x:tcvor){
        if(niz[x].size()&1){
            nfus++;
            if(x<=l){
                niz[x].pb(mp(l+r+1,nfus+m));
                niz[l+r+1].pb(mp(x,nfus+m));
            }else{
                niz[x].pb(mp(0,nfus+m));
                niz[0].pb(mp(x,nfus+m));
            }
        }
    }
    if(niz[0].size()&1){
        nfus++;
        niz[0].pb(mp(l+r+1,nfus+m));
        niz[l+r+1].pb(mp(0,nfus+m));
    }
    for(auto x:tcvor){
        //if(x==24)printf(" tst   %d %d   %d\n",x,dub,niz[x].size());

        if(obidjen[niz[x][0].S])continue;
        ojler(x,0,0,dub);

    }

    int gdep=lg;
    for(auto x:levi){
        if(!(x!=0 && x<=m))continue;
        temp[gdep]=x;
        gde[x]=gdep;
        gdep++;

    }
    int sppp=gdep-1;
    for(auto x:desni){
        if(!(x!=0 && x<=m))continue;
        temp[gdep]=x;
        gde[x]=gdep;
        gdep++;

    }
    for(int f=lg;f<=dg;f++){
        int x=pokom[f];
        obidjen[x]=false;
    }
    for(int i=m+1;i<=m+nfus;i++)obidjen[i]=false;

    for(auto x:tcvor)aktivan[x]=false;
    tcvor.clear();
    for(int f=lg;f<=dg;f++)pokom[f]=temp[f];
    resi(dub+1,lg,sppp);
    resi(dub+1,sppp+1,dg);
}


int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d %d %d", &l, &r, &m);
    for(int i=1;i<=m;i++){


        int t1,t2;
        scanf("%d %d", &t1, &t2);
        t2+=l;
        pocs[t1]++;
        pocs[t2]++;
        //printf("  %d %d\n",t1,t2);
        bboja=max(bboja,max(pocs[t1],pocs[t2]));
        grane[i]=(mp(t1,t2));
        pokom[i]=i;
        gde[i]=i;
    }
    int bbp=1;
    while((1<<bbp)<bboja)bbp++;
    maxd=bbp;
    bboja=1<<bbp;
    resi(0,1,m);
    printf("%d\n",bboja);
    for(int i=1;i<=m;i++)printf("%d\n",boje[i]+1);

    return 0;
}

Compilation message (stderr)

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 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