oj.uz

Submission #224542

# Submission time Handle Problem Language Result Execution time Memory
224542 2020-04-18T11:04:55 Z jhnah917 Saveit (IOI10_saveit) C++14
50 / 100
 255 ms 11968 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

int dst[44][1010];
vector<int> g[1010];
int par[1010];
int vis[1010];

void dfs(int v = 1){
    vis[v] = 1;
    for(auto i : g[v]) if(!vis[i]){
        par[i] = v; dfs(i);
    }
}

void bfs(int st){
    dst[st][st] = 0;
    queue<int> q; q.push(st);
    while(q.size()){
        int now = q.front(); q.pop();
        for(auto nxt : g[now]) if(dst[st][nxt] == -1){
            dst[st][nxt] = dst[st][now] + 1;
            q.push(nxt);
        }
    }
}

void encode(int N, int H, int M, int *v1, int *v2){
    int n = N, m = M, h = H;
    for(int i=0; i<m; i++){
        int s = v1[i] + 1, e = v2[i] + 1;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs();
    for(int i=2; i<=n; i++){
        for(int k=0; k<10; k++) encode_bit(!!(par[i] & (1 << k)));
    }
    memset(dst, -1, sizeof dst);
    for(int i=1; i<=h; i++) bfs(i);

    vector<int> v;
    for(int i=1; i<=h; i++) for(int j=2; j<=n; j++){
        int t = dst[i][j] - dst[i][par[j]];
        if(t == 1) encode_bit(0), encode_bit(0);
        else if(t == -1) encode_bit(1), encode_bit(1);
        else encode_bit(1), encode_bit(0);
        //v.push_back(dst[i][j] - dst[i][par[j]] + 1);
    }
}

//g++ grader.h grader.cpp encoder.h encoder.cpp decoder.h decoder.cpp -o main -std=c++14
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

/*
dst[i][j] - dst[i][par[j]]
1 : 0
-1 : 11
0 : 10
*/

int p[1010];
int mm[44][1010];
int chk[1010];
int ans[44][1010];

void go(int hh, int v){
    if(v == 1) return;
    if(!chk[p[v]]) go(hh, p[v]);
    ans[hh][v] = ans[hh][p[v]] + mm[hh][v];
    chk[v] = 1;
}

void decode(int N, int H) {
    int n = N, h = H;
    for(int i=2; i<=n; i++){
        for(int j=0; j<10; j++) p[i] += (decode_bit() << j);
    }
    for(int i=1; i<=h; i++) for(int j=2; j<=n; j++){
        int a = decode_bit(); int b = decode_bit();
        if(!a){ mm[i][j] = 1; continue; }
        if(b) mm[i][j] = -1;
        else mm[i][j] = 0;
    }
    for(int i=1; i<=h; i++){
        memset(chk, 0, sizeof chk);
        chk[1] = 1;
        for(int j=2; j<=n; j++) go(i, j);
    }
    for(int i=1; i<=h; i++) for(int j=1; j<=n; j++) hops(i-1, j-1, ans[i][j] - ans[i][i]);
}

//g++ grader.h grader.cpp encoder.h encoder.cpp decoder.h decoder.cpp -o main -std=c++14

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 11968 KB Output is partially correct - 81918 call(s) of encode_bit()
2 Correct 11 ms 5000 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 35 ms 5888 KB Output is partially correct - 73718 call(s) of encode_bit()
4 Correct 11 ms 4864 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 39 ms 6212 KB Output is partially correct - 73718 call(s) of encode_bit()
6 Correct 39 ms 6428 KB Output is partially correct - 81918 call(s) of encode_bit()
7 Correct 53 ms 6656 KB Output is partially correct - 81918 call(s) of encode_bit()
8 Correct 43 ms 6264 KB Output is partially correct - 78720 call(s) of encode_bit()
9 Correct 37 ms 6380 KB Output is partially correct - 81918 call(s) of encode_bit()
10 Correct 44 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
11 Correct 50 ms 6488 KB Output is partially correct - 81918 call(s) of encode_bit()
12 Correct 37 ms 6152 KB Output is partially correct - 81918 call(s) of encode_bit()
13 Correct 66 ms 6864 KB Output is partially correct - 81918 call(s) of encode_bit()
14 Correct 38 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
15 Correct 39 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
16 Correct 59 ms 6880 KB Output is partially correct - 81918 call(s) of encode_bit()
17 Correct 58 ms 6528 KB Output is partially correct - 81918 call(s) of encode_bit()
18 Correct 66 ms 7012 KB Output is partially correct - 81918 call(s) of encode_bit()
19 Correct 48 ms 6400 KB Output is partially correct - 81918 call(s) of encode_bit()
20 Correct 78 ms 7172 KB Output is partially correct - 81918 call(s) of encode_bit()
21 Correct 94 ms 7388 KB Output is partially correct - 81918 call(s) of encode_bit()
22 Correct 63 ms 6776 KB Output is partially correct - 81918 call(s) of encode_bit()
23 Correct 89 ms 7544 KB Output is partially correct - 81918 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 11968 KB Output is partially correct - 81918 call(s) of encode_bit()
2 Correct 11 ms 5000 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 35 ms 5888 KB Output is partially correct - 73718 call(s) of encode_bit()
4 Correct 11 ms 4864 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 39 ms 6212 KB Output is partially correct - 73718 call(s) of encode_bit()
6 Correct 39 ms 6428 KB Output is partially correct - 81918 call(s) of encode_bit()
7 Correct 53 ms 6656 KB Output is partially correct - 81918 call(s) of encode_bit()
8 Correct 43 ms 6264 KB Output is partially correct - 78720 call(s) of encode_bit()
9 Correct 37 ms 6380 KB Output is partially correct - 81918 call(s) of encode_bit()
10 Correct 44 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
11 Correct 50 ms 6488 KB Output is partially correct - 81918 call(s) of encode_bit()
12 Correct 37 ms 6152 KB Output is partially correct - 81918 call(s) of encode_bit()
13 Correct 66 ms 6864 KB Output is partially correct - 81918 call(s) of encode_bit()
14 Correct 38 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
15 Correct 39 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
16 Correct 59 ms 6880 KB Output is partially correct - 81918 call(s) of encode_bit()
17 Correct 58 ms 6528 KB Output is partially correct - 81918 call(s) of encode_bit()
18 Correct 66 ms 7012 KB Output is partially correct - 81918 call(s) of encode_bit()
19 Correct 48 ms 6400 KB Output is partially correct - 81918 call(s) of encode_bit()
20 Correct 78 ms 7172 KB Output is partially correct - 81918 call(s) of encode_bit()
21 Correct 94 ms 7388 KB Output is partially correct - 81918 call(s) of encode_bit()
22 Correct 63 ms 6776 KB Output is partially correct - 81918 call(s) of encode_bit()
23 Correct 89 ms 7544 KB Output is partially correct - 81918 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 11968 KB Output is partially correct - 81918 call(s) of encode_bit()
2 Correct 11 ms 5000 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 35 ms 5888 KB Output is partially correct - 73718 call(s) of encode_bit()
4 Correct 11 ms 4864 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 39 ms 6212 KB Output is partially correct - 73718 call(s) of encode_bit()
6 Correct 39 ms 6428 KB Output is partially correct - 81918 call(s) of encode_bit()
7 Correct 53 ms 6656 KB Output is partially correct - 81918 call(s) of encode_bit()
8 Correct 43 ms 6264 KB Output is partially correct - 78720 call(s) of encode_bit()
9 Correct 37 ms 6380 KB Output is partially correct - 81918 call(s) of encode_bit()
10 Correct 44 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
11 Correct 50 ms 6488 KB Output is partially correct - 81918 call(s) of encode_bit()
12 Correct 37 ms 6152 KB Output is partially correct - 81918 call(s) of encode_bit()
13 Correct 66 ms 6864 KB Output is partially correct - 81918 call(s) of encode_bit()
14 Correct 38 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
15 Correct 39 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
16 Correct 59 ms 6880 KB Output is partially correct - 81918 call(s) of encode_bit()
17 Correct 58 ms 6528 KB Output is partially correct - 81918 call(s) of encode_bit()
18 Correct 66 ms 7012 KB Output is partially correct - 81918 call(s) of encode_bit()
19 Correct 48 ms 6400 KB Output is partially correct - 81918 call(s) of encode_bit()
20 Correct 78 ms 7172 KB Output is partially correct - 81918 call(s) of encode_bit()
21 Correct 94 ms 7388 KB Output is partially correct - 81918 call(s) of encode_bit()
22 Correct 63 ms 6776 KB Output is partially correct - 81918 call(s) of encode_bit()
23 Correct 89 ms 7544 KB Output is partially correct - 81918 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 11968 KB Output is partially correct - 81918 call(s) of encode_bit()
2 Correct 11 ms 5000 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 35 ms 5888 KB Output is partially correct - 73718 call(s) of encode_bit()
4 Correct 11 ms 4864 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 39 ms 6212 KB Output is partially correct - 73718 call(s) of encode_bit()
6 Correct 39 ms 6428 KB Output is partially correct - 81918 call(s) of encode_bit()
7 Correct 53 ms 6656 KB Output is partially correct - 81918 call(s) of encode_bit()
8 Correct 43 ms 6264 KB Output is partially correct - 78720 call(s) of encode_bit()
9 Correct 37 ms 6380 KB Output is partially correct - 81918 call(s) of encode_bit()
10 Correct 44 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
11 Correct 50 ms 6488 KB Output is partially correct - 81918 call(s) of encode_bit()
12 Correct 37 ms 6152 KB Output is partially correct - 81918 call(s) of encode_bit()
13 Correct 66 ms 6864 KB Output is partially correct - 81918 call(s) of encode_bit()
14 Correct 38 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
15 Correct 39 ms 6144 KB Output is partially correct - 81918 call(s) of encode_bit()
16 Correct 59 ms 6880 KB Output is partially correct - 81918 call(s) of encode_bit()
17 Correct 58 ms 6528 KB Output is partially correct - 81918 call(s) of encode_bit()
18 Correct 66 ms 7012 KB Output is partially correct - 81918 call(s) of encode_bit()
19 Correct 48 ms 6400 KB Output is partially correct - 81918 call(s) of encode_bit()
20 Correct 78 ms 7172 KB Output is partially correct - 81918 call(s) of encode_bit()
21 Correct 94 ms 7388 KB Output is partially correct - 81918 call(s) of encode_bit()
22 Correct 63 ms 6776 KB Output is partially correct - 81918 call(s) of encode_bit()
23 Correct 89 ms 7544 KB Output is partially correct - 81918 call(s) of encode_bit()