Submission #7682

#	Time	Username	Problem	Language	Result	Execution time	Memory
7682		baneling100	Saveit (IOI10_saveit)	C++98	75 / 100	342 ms	11784 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];

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 static Send(int X) {

    int i;

    for(i=0 ; i<8 ; i++) {
        if(X&(1<<i))
            encode_bit(1);
        else
            encode_bit(0);
    }
}

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

    int i, j, Temp1, Temp2, Cnt;

    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++) {
        Temp1=Anc[i];
        for(j=0 ; j<10 ; j++) {
            if(Temp1&(1<<j))
                encode_bit(1);
            else
                encode_bit(0);
        }
    }
    for(i=0 ; i<nh ; i++)
        BFS(i);
    for(i=1 ; i<nv ; i++) {
        Temp1=Cnt=0;
        Temp2=1;
        for(j=0 ; j<nh ; j++) {
            Cnt++;
            if(D[j][i]-D[j][Anc[i]]==1)
                Temp1+=2*Temp2;
            else if(D[j][i]-D[j][Anc[i]]==0)
                Temp1+=Temp2;
            Temp2*=3;
            if(!(Cnt%5)) {
                Send(Temp1);
                Temp1=0;
                Temp2=1;
            }
        }
        if(Cnt%5)
            Send(Temp1);
    }
}

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], B[5];

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 Decoding(int X) {

    int i, Temp;

    for(i=0 ; i<5 ; i++) {
        Temp=X%3;
        if(Temp==2)
            B[i]=1;
        else if(Temp==1)
            B[i]=0;
        else
            B[i]=-1;
        X/=3;
    }
}

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, X;

    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();
    X=(nh+4)/5;
    for(i=1 ; i<nv ; i++)
        for(j=0 ; j<X ; j++) {
            Temp1=0;
            Temp2=1;
            for(k=0 ; k<8 ; k++) {
                Temp1+=Temp2*decode_bit();
                Temp2*=2;
            }
            Decoding(Temp1);
            for(k=5*j ; k<5*j+5 && k<nh ; k++)
                D[k][i]=B[k-5*j];
        }
    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]);
}

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