oj.uz

Submission #7697

# Submission time Handle Problem Language Result Execution time Memory
7697 2014-08-14T12:54:12 Z baneling100 Saveit (IOI10_saveit) C++
100 / 100
 368 ms 11520 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], 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);
            }
    }
}

#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

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

# Verdict Execution time Memory Grader output
1 Correct 368 ms 11520 KB Output is correct - 64913 call(s) of encode_bit()
2 Correct 7 ms 4596 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 34 ms 5696 KB Output is correct - 60701 call(s) of encode_bit()
4 Correct 7 ms 4688 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 37 ms 5896 KB Output is correct - 58088 call(s) of encode_bit()
6 Correct 38 ms 5836 KB Output is correct - 62905 call(s) of encode_bit()
7 Correct 46 ms 6124 KB Output is correct - 52828 call(s) of encode_bit()
8 Correct 26 ms 5500 KB Output is correct - 52233 call(s) of encode_bit()
9 Correct 27 ms 5772 KB Output is correct - 50157 call(s) of encode_bit()
10 Correct 27 ms 5720 KB Output is correct - 49796 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 53513 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is correct - 55633 call(s) of encode_bit()
13 Correct 79 ms 6292 KB Output is correct - 60326 call(s) of encode_bit()
14 Correct 28 ms 5704 KB Output is correct - 58622 call(s) of encode_bit()
15 Correct 27 ms 5804 KB Output is correct - 64703 call(s) of encode_bit()
16 Correct 68 ms 6336 KB Output is correct - 63929 call(s) of encode_bit()
17 Correct 59 ms 6304 KB Output is correct - 62727 call(s) of encode_bit()
18 Correct 72 ms 6576 KB Output is correct - 64690 call(s) of encode_bit()
19 Correct 55 ms 6080 KB Output is correct - 64698 call(s) of encode_bit()
20 Correct 81 ms 6824 KB Output is correct - 65570 call(s) of encode_bit()
21 Correct 104 ms 6848 KB Output is correct - 66320 call(s) of encode_bit()
22 Correct 64 ms 6240 KB Output is correct - 55039 call(s) of encode_bit()
23 Correct 146 ms 7032 KB Output is correct - 58825 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 11520 KB Output is correct - 64913 call(s) of encode_bit()
2 Correct 7 ms 4596 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 34 ms 5696 KB Output is correct - 60701 call(s) of encode_bit()
4 Correct 7 ms 4688 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 37 ms 5896 KB Output is correct - 58088 call(s) of encode_bit()
6 Correct 38 ms 5836 KB Output is correct - 62905 call(s) of encode_bit()
7 Correct 46 ms 6124 KB Output is correct - 52828 call(s) of encode_bit()
8 Correct 26 ms 5500 KB Output is correct - 52233 call(s) of encode_bit()
9 Correct 27 ms 5772 KB Output is correct - 50157 call(s) of encode_bit()
10 Correct 27 ms 5720 KB Output is correct - 49796 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 53513 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is correct - 55633 call(s) of encode_bit()
13 Correct 79 ms 6292 KB Output is correct - 60326 call(s) of encode_bit()
14 Correct 28 ms 5704 KB Output is correct - 58622 call(s) of encode_bit()
15 Correct 27 ms 5804 KB Output is correct - 64703 call(s) of encode_bit()
16 Correct 68 ms 6336 KB Output is correct - 63929 call(s) of encode_bit()
17 Correct 59 ms 6304 KB Output is correct - 62727 call(s) of encode_bit()
18 Correct 72 ms 6576 KB Output is correct - 64690 call(s) of encode_bit()
19 Correct 55 ms 6080 KB Output is correct - 64698 call(s) of encode_bit()
20 Correct 81 ms 6824 KB Output is correct - 65570 call(s) of encode_bit()
21 Correct 104 ms 6848 KB Output is correct - 66320 call(s) of encode_bit()
22 Correct 64 ms 6240 KB Output is correct - 55039 call(s) of encode_bit()
23 Correct 146 ms 7032 KB Output is correct - 58825 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 11520 KB Output is correct - 64913 call(s) of encode_bit()
2 Correct 7 ms 4596 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 34 ms 5696 KB Output is correct - 60701 call(s) of encode_bit()
4 Correct 7 ms 4688 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 37 ms 5896 KB Output is correct - 58088 call(s) of encode_bit()
6 Correct 38 ms 5836 KB Output is correct - 62905 call(s) of encode_bit()
7 Correct 46 ms 6124 KB Output is correct - 52828 call(s) of encode_bit()
8 Correct 26 ms 5500 KB Output is correct - 52233 call(s) of encode_bit()
9 Correct 27 ms 5772 KB Output is correct - 50157 call(s) of encode_bit()
10 Correct 27 ms 5720 KB Output is correct - 49796 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 53513 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is correct - 55633 call(s) of encode_bit()
13 Correct 79 ms 6292 KB Output is correct - 60326 call(s) of encode_bit()
14 Correct 28 ms 5704 KB Output is correct - 58622 call(s) of encode_bit()
15 Correct 27 ms 5804 KB Output is correct - 64703 call(s) of encode_bit()
16 Correct 68 ms 6336 KB Output is correct - 63929 call(s) of encode_bit()
17 Correct 59 ms 6304 KB Output is correct - 62727 call(s) of encode_bit()
18 Correct 72 ms 6576 KB Output is correct - 64690 call(s) of encode_bit()
19 Correct 55 ms 6080 KB Output is correct - 64698 call(s) of encode_bit()
20 Correct 81 ms 6824 KB Output is correct - 65570 call(s) of encode_bit()
21 Correct 104 ms 6848 KB Output is correct - 66320 call(s) of encode_bit()
22 Correct 64 ms 6240 KB Output is correct - 55039 call(s) of encode_bit()
23 Correct 146 ms 7032 KB Output is correct - 58825 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 11520 KB Output is correct - 64913 call(s) of encode_bit()
2 Correct 7 ms 4596 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 34 ms 5696 KB Output is correct - 60701 call(s) of encode_bit()
4 Correct 7 ms 4688 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 37 ms 5896 KB Output is correct - 58088 call(s) of encode_bit()
6 Correct 38 ms 5836 KB Output is correct - 62905 call(s) of encode_bit()
7 Correct 46 ms 6124 KB Output is correct - 52828 call(s) of encode_bit()
8 Correct 26 ms 5500 KB Output is correct - 52233 call(s) of encode_bit()
9 Correct 27 ms 5772 KB Output is correct - 50157 call(s) of encode_bit()
10 Correct 27 ms 5720 KB Output is correct - 49796 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 53513 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is correct - 55633 call(s) of encode_bit()
13 Correct 79 ms 6292 KB Output is correct - 60326 call(s) of encode_bit()
14 Correct 28 ms 5704 KB Output is correct - 58622 call(s) of encode_bit()
15 Correct 27 ms 5804 KB Output is correct - 64703 call(s) of encode_bit()
16 Correct 68 ms 6336 KB Output is correct - 63929 call(s) of encode_bit()
17 Correct 59 ms 6304 KB Output is correct - 62727 call(s) of encode_bit()
18 Correct 72 ms 6576 KB Output is correct - 64690 call(s) of encode_bit()
19 Correct 55 ms 6080 KB Output is correct - 64698 call(s) of encode_bit()
20 Correct 81 ms 6824 KB Output is correct - 65570 call(s) of encode_bit()
21 Correct 104 ms 6848 KB Output is correct - 66320 call(s) of encode_bit()
22 Correct 64 ms 6240 KB Output is correct - 55039 call(s) of encode_bit()
23 Correct 146 ms 7032 KB Output is correct - 58825 call(s) of encode_bit()