oj.uz

Submission #336880

# Submission time Handle Problem Language Result Execution time Memory
336880 2020-12-17T06:29:28 Z thecodingwizard Saveit (IOI10_saveit) C++11
100 / 100
 264 ms 10980 KB 
#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#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);
    }
}

ll curNum = 0;
int curSz = 0;
ll curMult = 1;

// 59 bits can represent 37 nodes

void flushCodes() {
    if (curSz > 0) {
        F0R(i, 59) {
            if (curNum & (1LL << i)) encode_bit(1);
            else encode_bit(0);
        }
        curNum = 0;
        curSz = 0;
        curMult = 1;
    }
}

void sendCode(int x) {
    if (curSz == 37) flushCodes();
    assert(0 <= x && x <= 2);
    curNum += curMult*x;
    curMult *= 3;
    curSz++;
}

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);
            }
        }
        flushCodes();
    }

    return;
}

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#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;
}

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);
    }
}

queue<int> codeQueue;
int readCode() {
    if (codeQueue.size() == 0) {
        ll num = 0;
        F0R(i, 59) {
            int x = decode_bit();
            if (x == 1) num |= (1LL << i);
        }
        F0R(i, 37) {
            codeQueue.push(num%3);
            num /= 3;
        }
    }
    int x = codeQueue.front();
    codeQueue.pop();
    return x;
}

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();
        }
        while (!codeQueue.empty()) codeQueue.pop();

        dfs(0);

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 10980 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 3 ms 4868 KB Output is correct - 247 call(s) of encode_bit()
3 Correct 26 ms 5784 KB Output is correct - 62450 call(s) of encode_bit()
4 Correct 2 ms 4864 KB Output is correct - 385 call(s) of encode_bit()
5 Correct 30 ms 5728 KB Output is correct - 62450 call(s) of encode_bit()
6 Correct 41 ms 6256 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 49 ms 6624 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 26 ms 5804 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 28 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 36 ms 5908 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 27 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 61 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 32 ms 5748 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 37 ms 5856 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 118 ms 6368 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 47 ms 6304 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 60 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 41 ms 6320 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 77 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 83 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 57 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 84 ms 7164 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 10980 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 3 ms 4868 KB Output is correct - 247 call(s) of encode_bit()
3 Correct 26 ms 5784 KB Output is correct - 62450 call(s) of encode_bit()
4 Correct 2 ms 4864 KB Output is correct - 385 call(s) of encode_bit()
5 Correct 30 ms 5728 KB Output is correct - 62450 call(s) of encode_bit()
6 Correct 41 ms 6256 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 49 ms 6624 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 26 ms 5804 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 28 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 36 ms 5908 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 27 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 61 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 32 ms 5748 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 37 ms 5856 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 118 ms 6368 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 47 ms 6304 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 60 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 41 ms 6320 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 77 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 83 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 57 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 84 ms 7164 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 10980 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 3 ms 4868 KB Output is correct - 247 call(s) of encode_bit()
3 Correct 26 ms 5784 KB Output is correct - 62450 call(s) of encode_bit()
4 Correct 2 ms 4864 KB Output is correct - 385 call(s) of encode_bit()
5 Correct 30 ms 5728 KB Output is correct - 62450 call(s) of encode_bit()
6 Correct 41 ms 6256 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 49 ms 6624 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 26 ms 5804 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 28 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 36 ms 5908 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 27 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 61 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 32 ms 5748 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 37 ms 5856 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 118 ms 6368 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 47 ms 6304 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 60 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 41 ms 6320 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 77 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 83 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 57 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 84 ms 7164 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 10980 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 3 ms 4868 KB Output is correct - 247 call(s) of encode_bit()
3 Correct 26 ms 5784 KB Output is correct - 62450 call(s) of encode_bit()
4 Correct 2 ms 4864 KB Output is correct - 385 call(s) of encode_bit()
5 Correct 30 ms 5728 KB Output is correct - 62450 call(s) of encode_bit()
6 Correct 41 ms 6256 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 49 ms 6624 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 26 ms 5804 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 28 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 36 ms 5908 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 27 ms 5728 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 61 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 32 ms 5748 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 37 ms 5856 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 118 ms 6368 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 47 ms 6304 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 60 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 41 ms 6320 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 77 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 83 ms 6880 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 57 ms 6496 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 84 ms 7164 KB Output is correct - 67698 call(s) of encode_bit()