oj.uz

Submission #17608

# Submission time Handle Problem Language Result Execution time Memory
17608 2016-01-02T14:59:55 Z Namnamseo Saveit (IOI10_saveit) C++14
50 / 100
 337 ms 11632 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) for(j=0;j<i;++j) write_int(table[i][j]); // triangular table
    
    for(i=1;i<n;++i) write_int(parent[i]);
    
    int pc=0, zc=0, mc=0, tmp;
    for(i=h;i<n;++i){
        for(j=0;j<h;++j){
            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]=i;
    write_smallint(conv[0]);
    write_smallint(conv[1]);
    write_smallint(conv[2]);
    
    for(i=h;i<n;++i) for(j=0;j<h;++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) for(j=0;j<i;++j) table[i][j]=table[j][i]=read_int(); // triangular
    
    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=h;i<n;++i) for(j=0;j<h;++j){
        table[j][i]=read_pm();
    }
    
    for(i=1;i<n;++i){
        int me=queue[i];
        if(me<h) continue;
        for(j=0;j<h;++j) 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

# Verdict Execution time Memory Grader output
1 Correct 337 ms 11632 KB Output is partially correct - 77187 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 87 call(s) of encode_bit()
3 Correct 30 ms 5612 KB Output is partially correct - 70466 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 145 call(s) of encode_bit()
5 Correct 35 ms 5744 KB Output is partially correct - 70538 call(s) of encode_bit()
6 Correct 35 ms 6024 KB Output is partially correct - 78125 call(s) of encode_bit()
7 Correct 63 ms 6332 KB Output is partially correct - 82823 call(s) of encode_bit()
8 Correct 33 ms 5848 KB Output is partially correct - 82505 call(s) of encode_bit()
9 Correct 30 ms 5928 KB Output is partially correct - 84481 call(s) of encode_bit()
10 Correct 33 ms 5996 KB Output is partially correct - 84100 call(s) of encode_bit()
11 Correct 36 ms 6084 KB Output is partially correct - 82427 call(s) of encode_bit()
12 Correct 33 ms 5984 KB Output is partially correct - 85703 call(s) of encode_bit()
13 Correct 53 ms 6564 KB Output is partially correct - 81888 call(s) of encode_bit()
14 Correct 33 ms 5880 KB Output is partially correct - 84407 call(s) of encode_bit()
15 Correct 26 ms 5816 KB Output is partially correct - 81808 call(s) of encode_bit()
16 Correct 79 ms 6504 KB Output is partially correct - 78349 call(s) of encode_bit()
17 Correct 62 ms 6380 KB Output is partially correct - 79951 call(s) of encode_bit()
18 Correct 69 ms 6668 KB Output is partially correct - 78396 call(s) of encode_bit()
19 Correct 85 ms 6344 KB Output is partially correct - 80320 call(s) of encode_bit()
20 Correct 86 ms 6912 KB Output is partially correct - 75342 call(s) of encode_bit()
21 Correct 93 ms 6952 KB Output is partially correct - 78997 call(s) of encode_bit()
22 Correct 79 ms 6536 KB Output is partially correct - 83230 call(s) of encode_bit()
23 Correct 71 ms 7224 KB Output is partially correct - 80436 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 11632 KB Output is partially correct - 77187 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 87 call(s) of encode_bit()
3 Correct 30 ms 5612 KB Output is partially correct - 70466 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 145 call(s) of encode_bit()
5 Correct 35 ms 5744 KB Output is partially correct - 70538 call(s) of encode_bit()
6 Correct 35 ms 6024 KB Output is partially correct - 78125 call(s) of encode_bit()
7 Correct 63 ms 6332 KB Output is partially correct - 82823 call(s) of encode_bit()
8 Correct 33 ms 5848 KB Output is partially correct - 82505 call(s) of encode_bit()
9 Correct 30 ms 5928 KB Output is partially correct - 84481 call(s) of encode_bit()
10 Correct 33 ms 5996 KB Output is partially correct - 84100 call(s) of encode_bit()
11 Correct 36 ms 6084 KB Output is partially correct - 82427 call(s) of encode_bit()
12 Correct 33 ms 5984 KB Output is partially correct - 85703 call(s) of encode_bit()
13 Correct 53 ms 6564 KB Output is partially correct - 81888 call(s) of encode_bit()
14 Correct 33 ms 5880 KB Output is partially correct - 84407 call(s) of encode_bit()
15 Correct 26 ms 5816 KB Output is partially correct - 81808 call(s) of encode_bit()
16 Correct 79 ms 6504 KB Output is partially correct - 78349 call(s) of encode_bit()
17 Correct 62 ms 6380 KB Output is partially correct - 79951 call(s) of encode_bit()
18 Correct 69 ms 6668 KB Output is partially correct - 78396 call(s) of encode_bit()
19 Correct 85 ms 6344 KB Output is partially correct - 80320 call(s) of encode_bit()
20 Correct 86 ms 6912 KB Output is partially correct - 75342 call(s) of encode_bit()
21 Correct 93 ms 6952 KB Output is partially correct - 78997 call(s) of encode_bit()
22 Correct 79 ms 6536 KB Output is partially correct - 83230 call(s) of encode_bit()
23 Correct 71 ms 7224 KB Output is partially correct - 80436 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 11632 KB Output is partially correct - 77187 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 87 call(s) of encode_bit()
3 Correct 30 ms 5612 KB Output is partially correct - 70466 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 145 call(s) of encode_bit()
5 Correct 35 ms 5744 KB Output is partially correct - 70538 call(s) of encode_bit()
6 Correct 35 ms 6024 KB Output is partially correct - 78125 call(s) of encode_bit()
7 Correct 63 ms 6332 KB Output is partially correct - 82823 call(s) of encode_bit()
8 Correct 33 ms 5848 KB Output is partially correct - 82505 call(s) of encode_bit()
9 Correct 30 ms 5928 KB Output is partially correct - 84481 call(s) of encode_bit()
10 Correct 33 ms 5996 KB Output is partially correct - 84100 call(s) of encode_bit()
11 Correct 36 ms 6084 KB Output is partially correct - 82427 call(s) of encode_bit()
12 Correct 33 ms 5984 KB Output is partially correct - 85703 call(s) of encode_bit()
13 Correct 53 ms 6564 KB Output is partially correct - 81888 call(s) of encode_bit()
14 Correct 33 ms 5880 KB Output is partially correct - 84407 call(s) of encode_bit()
15 Correct 26 ms 5816 KB Output is partially correct - 81808 call(s) of encode_bit()
16 Correct 79 ms 6504 KB Output is partially correct - 78349 call(s) of encode_bit()
17 Correct 62 ms 6380 KB Output is partially correct - 79951 call(s) of encode_bit()
18 Correct 69 ms 6668 KB Output is partially correct - 78396 call(s) of encode_bit()
19 Correct 85 ms 6344 KB Output is partially correct - 80320 call(s) of encode_bit()
20 Correct 86 ms 6912 KB Output is partially correct - 75342 call(s) of encode_bit()
21 Correct 93 ms 6952 KB Output is partially correct - 78997 call(s) of encode_bit()
22 Correct 79 ms 6536 KB Output is partially correct - 83230 call(s) of encode_bit()
23 Correct 71 ms 7224 KB Output is partially correct - 80436 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 11632 KB Output is partially correct - 77187 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 87 call(s) of encode_bit()
3 Correct 30 ms 5612 KB Output is partially correct - 70466 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 145 call(s) of encode_bit()
5 Correct 35 ms 5744 KB Output is partially correct - 70538 call(s) of encode_bit()
6 Correct 35 ms 6024 KB Output is partially correct - 78125 call(s) of encode_bit()
7 Correct 63 ms 6332 KB Output is partially correct - 82823 call(s) of encode_bit()
8 Correct 33 ms 5848 KB Output is partially correct - 82505 call(s) of encode_bit()
9 Correct 30 ms 5928 KB Output is partially correct - 84481 call(s) of encode_bit()
10 Correct 33 ms 5996 KB Output is partially correct - 84100 call(s) of encode_bit()
11 Correct 36 ms 6084 KB Output is partially correct - 82427 call(s) of encode_bit()
12 Correct 33 ms 5984 KB Output is partially correct - 85703 call(s) of encode_bit()
13 Correct 53 ms 6564 KB Output is partially correct - 81888 call(s) of encode_bit()
14 Correct 33 ms 5880 KB Output is partially correct - 84407 call(s) of encode_bit()
15 Correct 26 ms 5816 KB Output is partially correct - 81808 call(s) of encode_bit()
16 Correct 79 ms 6504 KB Output is partially correct - 78349 call(s) of encode_bit()
17 Correct 62 ms 6380 KB Output is partially correct - 79951 call(s) of encode_bit()
18 Correct 69 ms 6668 KB Output is partially correct - 78396 call(s) of encode_bit()
19 Correct 85 ms 6344 KB Output is partially correct - 80320 call(s) of encode_bit()
20 Correct 86 ms 6912 KB Output is partially correct - 75342 call(s) of encode_bit()
21 Correct 93 ms 6952 KB Output is partially correct - 78997 call(s) of encode_bit()
22 Correct 79 ms 6536 KB Output is partially correct - 83230 call(s) of encode_bit()
23 Correct 71 ms 7224 KB Output is partially correct - 80436 call(s) of encode_bit()