oj.uz

Submission #271293

# Submission time Handle Problem Language Result Execution time Memory
271293 2020-08-18T05:33:36 Z 문홍윤(#5109) Saveit (IOI10_saveit) C++14
100 / 100
 268 ms 11504 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

static int n, h, m, par[1010];
static vector<int> link[1010];

static bool ch[1010];
static void dfs(int num){
    ch[num]=true;
    for(auto i:link[num]){
        if(ch[i])continue;
        par[i]=num;
        dfs(i);
    }
}

static void enc(int num){
    for(int i=0; i<10; i++){
        if(num&(1<<i))encode_bit(1);
        else encode_bit(0);
    }
}
static void enc2(int num){
    for(int i=0; i<5; i++){
        if(num&(1<<i))encode_bit(1);
        else encode_bit(0);
    }
}

static int que[1010], fr, re, dis[1010];

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n=nv, h=nh, m=ne;
    for(int i=0; i<m; i++){
        link[v1[i]+1].eb(v2[i]+1);
        link[v2[i]+1].eb(v1[i]+1);
    }
    dfs(1);
    for(int i=2; i<=n; i++)enc(par[i]);
    for(int i=1; i<=h; i++){
        memset(ch, 0, sizeof ch);
        que[re=1]=i;
        ch[i]=true;
        dis[i]=0;
        for(fr=1; fr<=re; fr++){
            for(auto i:link[que[fr]]){
                if(ch[i])continue;
                ch[i]=true;
                dis[i]=dis[que[fr]]+1;
                que[++re]=i;
            }
        }
        for(int j=2; j<=n; j+=3){
            int t=0;
            for(int k=2; k>=0; k--){
                t*=3;
                if(j+k>n)continue;
                int dif=dis[j+k]-dis[par[j+k]];
                if(dif==0)t++;
                if(dif==1)t+=2;
            }
            enc2(t);
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;

static int n, h;
static vector<pii> link[1010];
static int cnt[1010], dis[1010];

static int rd(){
    vector<int> bt;
    for(int i=0; i<10; i++)bt.eb(decode_bit());
    int ret=0;
    for(int i=9; i>=0; i--){ret*=2; ret+=bt[i];}
    return ret;
}
static int rd2(){
    vector<int> bt;
    for(int i=0; i<5; i++)bt.eb(decode_bit());
    int ret=0;
    for(int i=4; i>=0; i--){ret*=2; ret+=bt[i];}
    return ret;
}
static void dfs(int num, int par){
    for(auto i:link[num]){
        if(i.F==par)continue;
        if(i.F==i.S)dis[i.F]=dis[num]+cnt[i.S];
        else dis[i.F]=dis[num]-cnt[i.S];
        dfs(i.F, num);
    }
}

void decode(int nv, int nh){
    n=nv, h=nh;
    for(int i=2; i<=n; i++){
        int j=rd();
        link[i].eb(j, i);
        link[j].eb(i, i);
    }
    for(int i=1; i<=h; i++){
        int t;
        for(int j=2; j<=n; j++){
            if(j%3==2)t=rd2();
            if(t%3==0)cnt[j]=-1;
            if(t%3==1)cnt[j]=0;
            if(t%3==2)cnt[j]=1;
            t/=3;
        }
        dis[i]=0;
        dfs(i, 0);
        for(int j=1; j<=n; j++)hops(i-1, j-1, dis[j]);
    }
}

Compilation message

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:49:17: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |             if(t%3==0)cnt[j]=-1;
      |                ~^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 11504 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4864 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 32 ms 5516 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 4 ms 4784 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 35 ms 5792 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 45 ms 5760 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 62 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 34 ms 5632 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 36 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 35 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 40 ms 5632 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 34 ms 5736 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 83 ms 6468 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 39 ms 5824 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 35 ms 5620 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 67 ms 6108 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 52 ms 6116 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 76 ms 6412 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 54 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6680 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 6840 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 67 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 93 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 11504 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4864 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 32 ms 5516 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 4 ms 4784 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 35 ms 5792 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 45 ms 5760 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 62 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 34 ms 5632 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 36 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 35 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 40 ms 5632 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 34 ms 5736 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 83 ms 6468 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 39 ms 5824 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 35 ms 5620 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 67 ms 6108 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 52 ms 6116 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 76 ms 6412 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 54 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6680 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 6840 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 67 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 93 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 11504 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4864 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 32 ms 5516 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 4 ms 4784 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 35 ms 5792 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 45 ms 5760 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 62 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 34 ms 5632 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 36 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 35 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 40 ms 5632 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 34 ms 5736 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 83 ms 6468 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 39 ms 5824 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 35 ms 5620 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 67 ms 6108 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 52 ms 6116 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 76 ms 6412 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 54 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6680 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 6840 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 67 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 93 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 11504 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4864 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 32 ms 5516 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 4 ms 4784 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 35 ms 5792 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 45 ms 5760 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 62 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 34 ms 5632 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 36 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 35 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 40 ms 5632 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 34 ms 5736 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 83 ms 6468 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 39 ms 5824 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 35 ms 5620 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 67 ms 6108 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 52 ms 6116 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 76 ms 6412 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 54 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6680 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 6840 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 67 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 93 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()