oj.uz

Submission #167705

# Submission time Handle Problem Language Result Execution time Memory
167705 2019-12-09T17:57:41 Z rzbt Teoretičar (COCI18_teoreticar) C++14
130 / 130
 3990 ms 50148 KB 
#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[10*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;
int kek1,kek2;
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);
    int lmao=0;
    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()){
            if(grana==0){
                s.pop();
                continue;
            }
            //printf("   %d %d   %d\n",t,grana,znak);
            boje[grana]|=(znak<<dub);
            if(znak)desni.pb(grana);
            else levi.pb(grana);
            kek1=levi.size();
            kek2=desni.size();
            s.pop();
            znak=1-znak;
            lmao--;
            continue;
        }
        if(obidjen[niz[t].back().second]){
            niz[t].pop_back();
            continue;
        }
        s.push(niz[t].back());
        niz[t].pop_back();
        lmao++;
        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(niz[x].empty())continue;
        if(obidjen[niz[x][0].S])continue;
        ojler(x,0,0,dub);

    }

    int gdep=lg;
    for(int ii=0;ii<levi.size();ii++){
        int x=levi[ii];
        if(!(x>0 && x<=m))continue;
        temp[gdep]=x;
        gde[x]=gdep;
        gdep++;

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

    }
    levi.clear();
    desni.clear();
    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()
{
    desni.reserve(5*MAXN);
    levi.reserve(5*MAXN);
    //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

teoreticar.cpp: In function 'void resi(int, int, int)':
teoreticar.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int ii=0;ii<levi.size();ii++){
                  ~~^~~~~~~~~~~~
teoreticar.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int ii=0;ii<desni.size();ii++){
                  ~~^~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:158: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:163: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5624 KB Output is correct
2 Correct 11 ms 5496 KB Output is correct
3 Correct 13 ms 5752 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5496 KB Output is correct
2 Correct 11 ms 5496 KB Output is correct
3 Correct 13 ms 5624 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 30596 KB Output is correct
2 Correct 3580 ms 44392 KB Output is correct
3 Correct 996 ms 48032 KB Output is correct
4 Correct 431 ms 37240 KB Output is correct
5 Correct 407 ms 27364 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 30480 KB Output is correct
2 Correct 1374 ms 42320 KB Output is correct
3 Correct 2081 ms 48312 KB Output is correct
4 Correct 522 ms 37284 KB Output is correct
5 Correct 125 ms 11792 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2373 ms 39612 KB Output is correct
2 Correct 2396 ms 49324 KB Output is correct
3 Correct 108 ms 11796 KB Output is correct
4 Correct 796 ms 32156 KB Output is correct
5 Correct 150 ms 23276 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 32772 KB Output is correct
2 Correct 3867 ms 50148 KB Output is correct
3 Correct 2312 ms 48588 KB Output is correct
4 Correct 679 ms 36000 KB Output is correct
5 Correct 461 ms 37240 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 27992 KB Output is correct
2 Correct 3990 ms 44808 KB Output is correct
3 Correct 2877 ms 49660 KB Output is correct
4 Correct 679 ms 35952 KB Output is correct
5 Correct 883 ms 31340 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1026 ms 27836 KB Output is correct
2 Correct 3772 ms 44712 KB Output is correct
3 Correct 2108 ms 49320 KB Output is correct
4 Correct 160 ms 12920 KB Output is correct
5 Correct 814 ms 32192 KB Output is correct