oj.uz

답안 #17610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17610 2016-01-02T15:46:37 Z Namnamseo 저장 (Saveit) (IOI10_saveit) C++14
100 / 100
 408 ms 11640 KB 
#include "grader.h"
#include "encoder.h"
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> pp;

static vector<int> e[1000];

static int vis[1000];
static int nowtime;
static int table[36][1000];
static int queue[1000];
static int parent[1000];

static int conv[3];

void input(int&ne, int*&v1, int*&v2){
    int a,b;
    for(;ne--;){
        a=v1[ne]; b=v2[ne];
        e[a].push_back(b);
        e[b].push_back(a);
    }
}

void bfs(int s) {
    ++nowtime; vis[s]=nowtime;
    queue[0]=s;
    parent[0]=-1;
    int head=1, tail=0;
    int i,sz,nxt,me;
    while(tail<head){
        me=queue[tail++];
        sz=e[me].size();
        for(i=0;i<sz;++i){
            nxt=e[me][i];
            if(vis[nxt]!=nowtime){
                vis[nxt]=nowtime;
                if(s==0) parent[nxt]=me;
                table[s][nxt]=table[s][me]+1;
                queue[head++]=nxt;
            }
        }
    }
}

inline void write_int(int x){
    for(int i=9;0<=i;--i) encode_bit(1&(x>>i));
}

inline void write_smallint(int x){
    if(x==0) encode_bit(0);
    else if(x==1) encode_bit(1), encode_bit(0);
    else          encode_bit(1), encode_bit(1);
}

void encode(int n, int h, int ne, int *v1, int *v2){
    input(ne,v1,v2);
    
    int i;
    for(i=0;i<h;++i) bfs(i);
    
    int j;
    for(i=1;i<h;++i) write_int(table[i][0]); // triangular table

    for(i=1;i<n;++i) write_int(parent[i]);
    
    int pc=0, zc=0, mc=0, tmp;
    for(i=1;i<n;++i){
        for(j=0;j<h;++j){
            if(i==j || (parent[i]==0 && j==0)) continue;
            tmp=table[j][i]-table[j][parent[i]];
            if(tmp==0) ++zc;
            else if(tmp>0) ++pc;
            else ++mc;
        }
    }
    
    pp sorter[3]={{zc,0},{pc,1},{mc,-1}};
    sort(sorter,sorter+3);

    for(i=0;i<3;++i) conv[sorter[i].second+1]=2-i;
    write_smallint(conv[0]);
    write_smallint(conv[1]);
    write_smallint(conv[2]);
    
    for(i=1;i<n;++i) for(j=0;j<h;++j){
        if(parent[i]==0 && j==0){
            write_int(table[j][i]);
        } else if(i!=j){
            tmp=table[j][i]-table[j][parent[i]];
            if(tmp==0) write_smallint(conv[1]);
            else if(tmp>0) write_smallint(conv[2]);
            else write_smallint(conv[0]);
        }
    }
}

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

inline int read_int(){
    int ret=0; for(int i=0;i<10;++i) ret=((ret<<1)|(decode_bit())); return ret;
}

static int table[36][1000];
static int parent[1000];

static int conv[3];

inline int read_smallint(){
    if(decode_bit()==0) return 0;
    else if(decode_bit()==0) return 1;
    else return 2;
}

inline int read_pm(){
    int tmp=read_smallint();
    if(conv[0]==tmp) return -1;
    else if(conv[1]==tmp) return 0;
    else return 1;
}

static std::vector<int> edge[1000];
static int queue[1000];

void topo(){
    int head=0, tail=0;
    queue[head++]=0;
    while(tail<head){
        int me=queue[tail++];
        int sz = edge[me].size();
        for(int i=0;i<sz;++i){
            int that=edge[me][i];
            queue[head++]=that;
        }
    }
}

void decode(int n, int h) {
    int i,j;
    for(i=1;i<h;++i) table[i][0]=read_int(); // zeroth column

    for(i=1;i<n;++i) parent[i]=read_int(), edge[parent[i]].push_back(i); // parent
    topo();

    for(i=0;i<3;++i) conv[i]=read_smallint();
    
    for(i=1;i<n;++i) for(j=0;j<h;++j){
        if(parent[i]==0 && j==0){
            table[j][i]=read_int();
            //printf("Getting %d,%d is big ; %d\n",j,i,table[j][i]);
        } else if(i!=j) table[j][i]=read_pm();
    }
    
    for(i=1;i<n;++i){
        int me=queue[i];
        for(j=0;j<h;++j){
            if(me==j || (parent[me]==0 && j==0)) continue;
            table[j][me]+=table[j][parent[me]];
        }
    }
    
    for(i=0;i<h;++i) for(j=0;j<n;++j) hops(i,j,table[i][j]);
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 408 ms 11640 KB Output is correct - 68795 call(s) of encode_bit()
2 Correct 7 ms 4592 KB Output is correct - 113 call(s) of encode_bit()
3 Correct 28 ms 5692 KB Output is correct - 61138 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 139 call(s) of encode_bit()
5 Correct 35 ms 5692 KB Output is correct - 58609 call(s) of encode_bit()
6 Correct 34 ms 5820 KB Output is correct - 63214 call(s) of encode_bit()
7 Correct 79 ms 6016 KB Output is correct - 53405 call(s) of encode_bit()
8 Correct 26 ms 5692 KB Output is correct - 54074 call(s) of encode_bit()
9 Correct 27 ms 5564 KB Output is correct - 50458 call(s) of encode_bit()
10 Correct 27 ms 5564 KB Output is correct - 50709 call(s) of encode_bit()
11 Correct 36 ms 5744 KB Output is correct - 53836 call(s) of encode_bit()
12 Correct 32 ms 5692 KB Output is correct - 55934 call(s) of encode_bit()
13 Correct 84 ms 6336 KB Output is correct - 60203 call(s) of encode_bit()
14 Correct 31 ms 5696 KB Output is correct - 58645 call(s) of encode_bit()
15 Correct 35 ms 5836 KB Output is correct - 65399 call(s) of encode_bit()
16 Correct 59 ms 6256 KB Output is correct - 62195 call(s) of encode_bit()
17 Correct 52 ms 6124 KB Output is correct - 64300 call(s) of encode_bit()
18 Correct 107 ms 6436 KB Output is correct - 65286 call(s) of encode_bit()
19 Correct 53 ms 6220 KB Output is correct - 67114 call(s) of encode_bit()
20 Correct 55 ms 6824 KB Output is correct - 68051 call(s) of encode_bit()
21 Correct 124 ms 6888 KB Output is correct - 67970 call(s) of encode_bit()
22 Correct 62 ms 6508 KB Output is correct - 56554 call(s) of encode_bit()
23 Correct 108 ms 7160 KB Output is correct - 59951 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 408 ms 11640 KB Output is correct - 68795 call(s) of encode_bit()
2 Correct 7 ms 4592 KB Output is correct - 113 call(s) of encode_bit()
3 Correct 28 ms 5692 KB Output is correct - 61138 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 139 call(s) of encode_bit()
5 Correct 35 ms 5692 KB Output is correct - 58609 call(s) of encode_bit()
6 Correct 34 ms 5820 KB Output is correct - 63214 call(s) of encode_bit()
7 Correct 79 ms 6016 KB Output is correct - 53405 call(s) of encode_bit()
8 Correct 26 ms 5692 KB Output is correct - 54074 call(s) of encode_bit()
9 Correct 27 ms 5564 KB Output is correct - 50458 call(s) of encode_bit()
10 Correct 27 ms 5564 KB Output is correct - 50709 call(s) of encode_bit()
11 Correct 36 ms 5744 KB Output is correct - 53836 call(s) of encode_bit()
12 Correct 32 ms 5692 KB Output is correct - 55934 call(s) of encode_bit()
13 Correct 84 ms 6336 KB Output is correct - 60203 call(s) of encode_bit()
14 Correct 31 ms 5696 KB Output is correct - 58645 call(s) of encode_bit()
15 Correct 35 ms 5836 KB Output is correct - 65399 call(s) of encode_bit()
16 Correct 59 ms 6256 KB Output is correct - 62195 call(s) of encode_bit()
17 Correct 52 ms 6124 KB Output is correct - 64300 call(s) of encode_bit()
18 Correct 107 ms 6436 KB Output is correct - 65286 call(s) of encode_bit()
19 Correct 53 ms 6220 KB Output is correct - 67114 call(s) of encode_bit()
20 Correct 55 ms 6824 KB Output is correct - 68051 call(s) of encode_bit()
21 Correct 124 ms 6888 KB Output is correct - 67970 call(s) of encode_bit()
22 Correct 62 ms 6508 KB Output is correct - 56554 call(s) of encode_bit()
23 Correct 108 ms 7160 KB Output is correct - 59951 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 408 ms 11640 KB Output is correct - 68795 call(s) of encode_bit()
2 Correct 7 ms 4592 KB Output is correct - 113 call(s) of encode_bit()
3 Correct 28 ms 5692 KB Output is correct - 61138 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 139 call(s) of encode_bit()
5 Correct 35 ms 5692 KB Output is correct - 58609 call(s) of encode_bit()
6 Correct 34 ms 5820 KB Output is correct - 63214 call(s) of encode_bit()
7 Correct 79 ms 6016 KB Output is correct - 53405 call(s) of encode_bit()
8 Correct 26 ms 5692 KB Output is correct - 54074 call(s) of encode_bit()
9 Correct 27 ms 5564 KB Output is correct - 50458 call(s) of encode_bit()
10 Correct 27 ms 5564 KB Output is correct - 50709 call(s) of encode_bit()
11 Correct 36 ms 5744 KB Output is correct - 53836 call(s) of encode_bit()
12 Correct 32 ms 5692 KB Output is correct - 55934 call(s) of encode_bit()
13 Correct 84 ms 6336 KB Output is correct - 60203 call(s) of encode_bit()
14 Correct 31 ms 5696 KB Output is correct - 58645 call(s) of encode_bit()
15 Correct 35 ms 5836 KB Output is correct - 65399 call(s) of encode_bit()
16 Correct 59 ms 6256 KB Output is correct - 62195 call(s) of encode_bit()
17 Correct 52 ms 6124 KB Output is correct - 64300 call(s) of encode_bit()
18 Correct 107 ms 6436 KB Output is correct - 65286 call(s) of encode_bit()
19 Correct 53 ms 6220 KB Output is correct - 67114 call(s) of encode_bit()
20 Correct 55 ms 6824 KB Output is correct - 68051 call(s) of encode_bit()
21 Correct 124 ms 6888 KB Output is correct - 67970 call(s) of encode_bit()
22 Correct 62 ms 6508 KB Output is correct - 56554 call(s) of encode_bit()
23 Correct 108 ms 7160 KB Output is correct - 59951 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 408 ms 11640 KB Output is correct - 68795 call(s) of encode_bit()
2 Correct 7 ms 4592 KB Output is correct - 113 call(s) of encode_bit()
3 Correct 28 ms 5692 KB Output is correct - 61138 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 139 call(s) of encode_bit()
5 Correct 35 ms 5692 KB Output is correct - 58609 call(s) of encode_bit()
6 Correct 34 ms 5820 KB Output is correct - 63214 call(s) of encode_bit()
7 Correct 79 ms 6016 KB Output is correct - 53405 call(s) of encode_bit()
8 Correct 26 ms 5692 KB Output is correct - 54074 call(s) of encode_bit()
9 Correct 27 ms 5564 KB Output is correct - 50458 call(s) of encode_bit()
10 Correct 27 ms 5564 KB Output is correct - 50709 call(s) of encode_bit()
11 Correct 36 ms 5744 KB Output is correct - 53836 call(s) of encode_bit()
12 Correct 32 ms 5692 KB Output is correct - 55934 call(s) of encode_bit()
13 Correct 84 ms 6336 KB Output is correct - 60203 call(s) of encode_bit()
14 Correct 31 ms 5696 KB Output is correct - 58645 call(s) of encode_bit()
15 Correct 35 ms 5836 KB Output is correct - 65399 call(s) of encode_bit()
16 Correct 59 ms 6256 KB Output is correct - 62195 call(s) of encode_bit()
17 Correct 52 ms 6124 KB Output is correct - 64300 call(s) of encode_bit()
18 Correct 107 ms 6436 KB Output is correct - 65286 call(s) of encode_bit()
19 Correct 53 ms 6220 KB Output is correct - 67114 call(s) of encode_bit()
20 Correct 55 ms 6824 KB Output is correct - 68051 call(s) of encode_bit()
21 Correct 124 ms 6888 KB Output is correct - 67970 call(s) of encode_bit()
22 Correct 62 ms 6508 KB Output is correct - 56554 call(s) of encode_bit()
23 Correct 108 ms 7160 KB Output is correct - 59951 call(s) of encode_bit()