Submission #7697

#	Time	Username	Problem	Language	Result	Execution time	Memory
7697		baneling100	Saveit (IOI10_saveit)	C++98	100 / 100	368 ms	11520 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>

using namespace std;

static queue <int> Q;
static vector <int> A[1000];
static int nv, nh, ne, Anc[1000], Check[1000], D[36][1000], Plus, Zero, Minus;

void static MakeAnc(void) {

    int i, j, Now;

    Q.push(0);
    Check[0]=1;
    while(!Q.empty()) {
        Now=Q.front();
        Q.pop();
        j=A[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[A[Now][i]]) {
                Check[A[Now][i]]=1;
                Anc[A[Now][i]]=Now;
                Q.push(A[Now][i]);
            }
    }
}

void static BFS(int S) {

    int i, j, Now;

    for(i=0 ; i<nv ; i++)
        Check[i]=0;
    Check[S]=1;
    D[S][S]=0;
    Q.push(S);
    while(!Q.empty()) {
        Now=Q.front();
        Q.pop();
        j=A[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[A[Now][i]]) {
                Check[A[Now][i]]=1;
                D[S][A[Now][i]]=D[S][Now]+1;
                Q.push(A[Now][i]);
            }
    }
}

void encode(int nv_, int nh_, int ne_, int *v1, int *v2) {

    int i, j;

    nv=nv_;
    nh=nh_;
    ne=ne_;
    for(i=0 ; i<ne ; i++) {
        A[v1[i]].push_back(v2[i]);
        A[v2[i]].push_back(v1[i]);
    }
    MakeAnc();
    for(i=1 ; i<nv ; i++)
        for(j=0 ; j<10 ; j++) {
            if(Anc[i]&(1<<j))
                encode_bit(1);
            else
                encode_bit(0);
        }
    for(i=0 ; i<nh ; i++)
        BFS(i);
    for(i=1 ; i<nv ; i++)
        for(j=0 ; j<nh ; j++) {
            if(D[j][i]-D[j][Anc[i]]==1)
                Plus++;
            else if(D[j][i]-D[j][Anc[i]]==0)
                Zero++;
            else
                Minus++;
        }
    if(Plus>=Zero && Plus>=Minus) {
        encode_bit(0);
        encode_bit(0);
        for(i=1 ; i<nv ; i++)
            for(j=0 ; j<nh ; j++) {
                if(D[j][i]-D[j][Anc[i]]==1)
                    encode_bit(0);
                else if(D[j][i]-D[j][Anc[i]]==0) {
                    encode_bit(1);
                    encode_bit(0);
                }
                else {
                    encode_bit(1);
                    encode_bit(1);
                }
            }
    }
    else if(Zero>=Plus && Zero>=Minus) {
        encode_bit(1);
        encode_bit(0);
        for(i=1 ; i<nv ; i++)
            for(j=0 ; j<nh ; j++) {
                if(D[j][i]-D[j][Anc[i]]==1) {
                    encode_bit(1);
                    encode_bit(0);
                }
                else if(D[j][i]-D[j][Anc[i]]==0)
                    encode_bit(0);
                else {
                    encode_bit(1);
                    encode_bit(1);
                }
            }
    }
    else {
        encode_bit(1);
        encode_bit(1);
        for(i=1 ; i<nv ; i++)
            for(j=0 ; j<nh ; j++) {
                if(D[j][i]-D[j][Anc[i]]==1) {
                    encode_bit(1);
                    encode_bit(0);
                }
                else if(D[j][i]-D[j][Anc[i]]==0) {
                    encode_bit(1);
                    encode_bit(1);
                }
                else
                    encode_bit(0);
            }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <vector>
#include <queue>

using namespace std;

static vector <int> A[1000];
static queue <int> Q;
static int nv, nh, Anc[1000], D[36][1000], Check[1000];

void static BFS(void) {

    int i, j, Now, Dist;

    Q.push(0);
    Q.push(0);
    Check[0]=1;
    D[0][0]=0;
    while(!Q.empty()) {
        Now=Q.front();
        Q.pop();
        Dist=Q.front();
        Q.pop();
        if(Now<nh)
            D[Now][0]=Dist;
        j=A[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[A[Now][i]]) {
                Check[A[Now][i]]=1;
                Q.push(A[Now][i]);
                Q.push(Dist+1);
            }
    }
}

void static DFS(int Now) {

    int i, j=A[Now].size(), k;

    for(i=0 ; i<j ; i++)
        if(!Check[A[Now][i]]) {
            Check[A[Now][i]]=1;
            for(k=0 ; k<nh ; k++)
                D[k][A[Now][i]]+=D[k][Now];
            DFS(A[Now][i]);
        }
}

void decode(int nv_, int nh_) {

    int i, j, k, Temp1, Temp2, Type1, Type2;

    nv=nv_;
    nh=nh_;
    for(i=1 ; i<nv ; i++) {
        Temp1=0;
        Temp2=1;
        for(j=0 ; j<10 ; j++) {
            Temp1+=Temp2*decode_bit();
            Temp2*=2;
        }
        A[i].push_back(Temp1);
        A[Temp1].push_back(i);
        Anc[i]=Temp1;
    }
    BFS();
    Type1=decode_bit();
    Type2=decode_bit();
    if(Type1) {
        if(Type2) {
            for(i=1 ; i<nv ; i++)
                for(j=0 ; j<nh ; j++) {
                    Temp1=decode_bit();
                    if(Temp1) {
                        Temp2=decode_bit();
                        if(Temp2)
                            D[j][i]=0;
                        else
                            D[j][i]=1;
                    }
                    else
                        D[j][i]=-1;
                }
        }
        else {
            for(i=1 ; i<nv ; i++)
                for(j=0 ; j<nh ; j++) {
                    Temp1=decode_bit();
                    if(Temp1) {
                        Temp2=decode_bit();
                        if(Temp2)
                            D[j][i]=-1;
                        else
                            D[j][i]=1;
                    }
                    else
                        D[j][i]=0;
                }
        }
    }
    else {
        for(i=1 ; i<nv ; i++)
            for(j=0 ; j<nh ; j++) {
                Temp1=decode_bit();
                if(Temp1) {
                    Temp2=decode_bit();
                    if(Temp2)
                        D[j][i]=-1;
                    else
                        D[j][i]=0;
                }
                else
                    D[j][i]=1;
            }
    }
    for(i=0 ; i<nv ; i++)
        Check[i]=0;
    Check[0]=1;
    DFS(0);
    for(i=0 ; i<nh ; i++)
        for(j=0 ; j<nv ; j++)
            hops(i,j,D[i][j]);
}

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:52:15: warning: unused variable 'k' [-Wunused-variable]
     int i, j, k, Temp1, Temp2, Type1, Type2;
               ^

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25