oj.uz

Submission #336875

# Submission time Handle Problem Language Result Execution time Memory
336875 2020-12-17T06:17:23 Z thecodingwizard Saveit (IOI10_saveit) C++11
50 / 100
 281 ms 10940 KB 
#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define pb push_back
#define inf 1000000010
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

void sendNum(int x) {
    assert(x <= 1023);
    F0R(i, 10) {
        if (x&(1<<i)) encode_bit(1);
        else encode_bit(0);
    }
}

vector<int> adj[1000];
int pa[1000];
int dist[36][1000];

void dfs(int u, int p) {
    pa[u] = p;
    for (int v : adj[u]) {
        if (pa[v] == -1) dfs(v, u);
    }
}

void sendCode(int x) {
    assert(0 <= x && x <= 2);
    if (x==0) {
        encode_bit(0);
        encode_bit(0);
    } else if (x == 1) {
        encode_bit(0);
        encode_bit(1);
    } else {
        encode_bit(1);
        encode_bit(0);
    }
}

void encode(int n, int h, int e, int *v1, int *v2){
    F0R(i, e) {
        adj[v1[i]].pb(v2[i]);
        adj[v2[i]].pb(v1[i]);
    }
    F0R(i, n) pa[i] = -1;

    dfs(0, 0);

    FOR(i, 1, n) {
        sendNum(pa[i]);
    }

    F0R(i, 36) {
        F0R(j, n) dist[i][j] = inf;
        dist[i][i] = 0;
        queue<int> q; q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (dist[i][v] == inf) {
                    dist[i][v] = dist[i][u]+1;
                    q.push(v);
                }
            }
        }
    }

    F0R(i, h) {
        sendNum(dist[i][0]);
        FOR(j, 1, n) {
            int p = pa[j];
            if (dist[i][j] == dist[i][p]) {
                sendCode(0);
            } else if (dist[i][j] == dist[i][p]+1) {
                sendCode(1);
            } else if (dist[i][j] == dist[i][p]-1) {
                sendCode(2);
            } else {
                cout << i << " " << j << " " << p << endl;
                cout << dist[i][j] << " " << dist[i][p] << endl;
                cerr << "??" << endl;
                exit(1);
            }
        }
    }

    return;
}

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define pb push_back
#define inf 1000000010
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

int ans[1000], codes[1000];
vector<int> children[1000];

int readNum() {
    int n = 0;
    F0R(i, 10) {
        int x = decode_bit();
        if (x) n |= (1 << i);
    }
    return n;
}

int readCode() {
    int a = decode_bit(), b = decode_bit();
    if (a == 0 && b == 0) return 0;
    if (a == 0 && b == 1) return 1;
    if (a == 1 && b == 0) return 2;
    assert(false);
}

void dfs(int u) {
    for (int v : children[u]) {
        int code = codes[v];
        if (code == 0) ans[v] = ans[u];
        else if (code == 1) ans[v] = ans[u]+1;
        else if (code == 2) ans[v] = ans[u]-1;
        else assert(false);
        dfs(v);
    }
}

void decode(int n, int h) {
    int pa[1000];

    FOR(i, 1, n) {
        pa[i] = readNum();
        children[pa[i]].pb(i);
    }
    F0R(i, h) {
        ans[0] = readNum();

        FOR(j, 1, n) {
            codes[j] = readCode();
        }

        dfs(0);

        F0R(j, n) {
            hops(i, j, ans[j]);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10940 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4916 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 5600 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 3 ms 4936 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 43 ms 5984 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 35 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 52 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 30 ms 5984 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 30 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 32 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 40 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 34 ms 5728 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 66 ms 6496 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 31 ms 5964 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 36 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 61 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 54 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 66 ms 6572 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 46 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 79 ms 6940 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 86 ms 7060 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 55 ms 6684 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 93 ms 7264 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10940 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4916 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 5600 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 3 ms 4936 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 43 ms 5984 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 35 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 52 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 30 ms 5984 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 30 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 32 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 40 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 34 ms 5728 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 66 ms 6496 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 31 ms 5964 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 36 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 61 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 54 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 66 ms 6572 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 46 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 79 ms 6940 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 86 ms 7060 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 55 ms 6684 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 93 ms 7264 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10940 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4916 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 5600 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 3 ms 4936 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 43 ms 5984 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 35 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 52 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 30 ms 5984 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 30 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 32 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 40 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 34 ms 5728 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 66 ms 6496 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 31 ms 5964 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 36 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 61 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 54 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 66 ms 6572 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 46 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 79 ms 6940 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 86 ms 7060 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 55 ms 6684 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 93 ms 7264 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10940 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4916 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 5600 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 3 ms 4936 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 43 ms 5984 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 35 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 52 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 30 ms 5984 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 30 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 32 ms 5856 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 40 ms 5984 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 34 ms 5728 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 66 ms 6496 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 31 ms 5964 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 36 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 61 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 54 ms 6368 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 66 ms 6572 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 46 ms 6112 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 79 ms 6940 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 86 ms 7060 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 55 ms 6684 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 93 ms 7264 KB Output is partially correct - 82278 call(s) of encode_bit()