oj.uz

Submission #7682

# Submission time Handle Problem Language Result Execution time Memory
7682 2014-08-14T06:56:32 Z baneling100 Saveit (IOI10_saveit) C++
75 / 100
 342 ms 11784 KB 
#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);
    }
}

#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 11784 KB Output is partially correct - 73926 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 40 ms 5652 KB Output is correct - 66526 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 54 ms 5916 KB Output is correct - 66526 call(s) of encode_bit()
6 Correct 40 ms 5956 KB Output is partially correct - 73926 call(s) of encode_bit()
7 Correct 46 ms 6380 KB Output is partially correct - 73926 call(s) of encode_bit()
8 Correct 33 ms 5744 KB Output is partially correct - 71040 call(s) of encode_bit()
9 Correct 37 ms 5924 KB Output is partially correct - 73926 call(s) of encode_bit()
10 Correct 35 ms 5952 KB Output is partially correct - 73926 call(s) of encode_bit()
11 Correct 33 ms 5988 KB Output is partially correct - 73926 call(s) of encode_bit()
12 Correct 31 ms 5832 KB Output is partially correct - 73926 call(s) of encode_bit()
13 Correct 65 ms 6484 KB Output is partially correct - 73926 call(s) of encode_bit()
14 Correct 33 ms 5828 KB Output is partially correct - 73926 call(s) of encode_bit()
15 Correct 32 ms 5872 KB Output is partially correct - 73926 call(s) of encode_bit()
16 Correct 76 ms 6328 KB Output is partially correct - 73926 call(s) of encode_bit()
17 Correct 64 ms 6276 KB Output is partially correct - 73926 call(s) of encode_bit()
18 Correct 71 ms 6512 KB Output is partially correct - 73926 call(s) of encode_bit()
19 Correct 48 ms 6144 KB Output is partially correct - 73926 call(s) of encode_bit()
20 Correct 94 ms 6908 KB Output is partially correct - 73926 call(s) of encode_bit()
21 Correct 101 ms 6804 KB Output is partially correct - 73926 call(s) of encode_bit()
22 Correct 78 ms 6404 KB Output is partially correct - 73926 call(s) of encode_bit()
23 Correct 99 ms 7096 KB Output is partially correct - 73926 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 11784 KB Output is partially correct - 73926 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 40 ms 5652 KB Output is correct - 66526 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 54 ms 5916 KB Output is correct - 66526 call(s) of encode_bit()
6 Correct 40 ms 5956 KB Output is partially correct - 73926 call(s) of encode_bit()
7 Correct 46 ms 6380 KB Output is partially correct - 73926 call(s) of encode_bit()
8 Correct 33 ms 5744 KB Output is partially correct - 71040 call(s) of encode_bit()
9 Correct 37 ms 5924 KB Output is partially correct - 73926 call(s) of encode_bit()
10 Correct 35 ms 5952 KB Output is partially correct - 73926 call(s) of encode_bit()
11 Correct 33 ms 5988 KB Output is partially correct - 73926 call(s) of encode_bit()
12 Correct 31 ms 5832 KB Output is partially correct - 73926 call(s) of encode_bit()
13 Correct 65 ms 6484 KB Output is partially correct - 73926 call(s) of encode_bit()
14 Correct 33 ms 5828 KB Output is partially correct - 73926 call(s) of encode_bit()
15 Correct 32 ms 5872 KB Output is partially correct - 73926 call(s) of encode_bit()
16 Correct 76 ms 6328 KB Output is partially correct - 73926 call(s) of encode_bit()
17 Correct 64 ms 6276 KB Output is partially correct - 73926 call(s) of encode_bit()
18 Correct 71 ms 6512 KB Output is partially correct - 73926 call(s) of encode_bit()
19 Correct 48 ms 6144 KB Output is partially correct - 73926 call(s) of encode_bit()
20 Correct 94 ms 6908 KB Output is partially correct - 73926 call(s) of encode_bit()
21 Correct 101 ms 6804 KB Output is partially correct - 73926 call(s) of encode_bit()
22 Correct 78 ms 6404 KB Output is partially correct - 73926 call(s) of encode_bit()
23 Correct 99 ms 7096 KB Output is partially correct - 73926 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 11784 KB Output is partially correct - 73926 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 40 ms 5652 KB Output is correct - 66526 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 54 ms 5916 KB Output is correct - 66526 call(s) of encode_bit()
6 Correct 40 ms 5956 KB Output is partially correct - 73926 call(s) of encode_bit()
7 Correct 46 ms 6380 KB Output is partially correct - 73926 call(s) of encode_bit()
8 Correct 33 ms 5744 KB Output is partially correct - 71040 call(s) of encode_bit()
9 Correct 37 ms 5924 KB Output is partially correct - 73926 call(s) of encode_bit()
10 Correct 35 ms 5952 KB Output is partially correct - 73926 call(s) of encode_bit()
11 Correct 33 ms 5988 KB Output is partially correct - 73926 call(s) of encode_bit()
12 Correct 31 ms 5832 KB Output is partially correct - 73926 call(s) of encode_bit()
13 Correct 65 ms 6484 KB Output is partially correct - 73926 call(s) of encode_bit()
14 Correct 33 ms 5828 KB Output is partially correct - 73926 call(s) of encode_bit()
15 Correct 32 ms 5872 KB Output is partially correct - 73926 call(s) of encode_bit()
16 Correct 76 ms 6328 KB Output is partially correct - 73926 call(s) of encode_bit()
17 Correct 64 ms 6276 KB Output is partially correct - 73926 call(s) of encode_bit()
18 Correct 71 ms 6512 KB Output is partially correct - 73926 call(s) of encode_bit()
19 Correct 48 ms 6144 KB Output is partially correct - 73926 call(s) of encode_bit()
20 Correct 94 ms 6908 KB Output is partially correct - 73926 call(s) of encode_bit()
21 Correct 101 ms 6804 KB Output is partially correct - 73926 call(s) of encode_bit()
22 Correct 78 ms 6404 KB Output is partially correct - 73926 call(s) of encode_bit()
23 Correct 99 ms 7096 KB Output is partially correct - 73926 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 11784 KB Output is partially correct - 73926 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 40 ms 5652 KB Output is correct - 66526 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 54 ms 5916 KB Output is correct - 66526 call(s) of encode_bit()
6 Correct 40 ms 5956 KB Output is partially correct - 73926 call(s) of encode_bit()
7 Correct 46 ms 6380 KB Output is partially correct - 73926 call(s) of encode_bit()
8 Correct 33 ms 5744 KB Output is partially correct - 71040 call(s) of encode_bit()
9 Correct 37 ms 5924 KB Output is partially correct - 73926 call(s) of encode_bit()
10 Correct 35 ms 5952 KB Output is partially correct - 73926 call(s) of encode_bit()
11 Correct 33 ms 5988 KB Output is partially correct - 73926 call(s) of encode_bit()
12 Correct 31 ms 5832 KB Output is partially correct - 73926 call(s) of encode_bit()
13 Correct 65 ms 6484 KB Output is partially correct - 73926 call(s) of encode_bit()
14 Correct 33 ms 5828 KB Output is partially correct - 73926 call(s) of encode_bit()
15 Correct 32 ms 5872 KB Output is partially correct - 73926 call(s) of encode_bit()
16 Correct 76 ms 6328 KB Output is partially correct - 73926 call(s) of encode_bit()
17 Correct 64 ms 6276 KB Output is partially correct - 73926 call(s) of encode_bit()
18 Correct 71 ms 6512 KB Output is partially correct - 73926 call(s) of encode_bit()
19 Correct 48 ms 6144 KB Output is partially correct - 73926 call(s) of encode_bit()
20 Correct 94 ms 6908 KB Output is partially correct - 73926 call(s) of encode_bit()
21 Correct 101 ms 6804 KB Output is partially correct - 73926 call(s) of encode_bit()
22 Correct 78 ms 6404 KB Output is partially correct - 73926 call(s) of encode_bit()
23 Correct 99 ms 7096 KB Output is partially correct - 73926 call(s) of encode_bit()