oj.uz

Submission #597447

# Submission time Handle Problem Language Result Execution time Memory
597447 2022-07-16T03:54:54 Z skittles1412 Saveit (IOI10_saveit) C++17
100 / 100
 267 ms 10492 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

void encode_bit(int b);

void write(int bits, long x) {
    for (int i = 0; i < bits; i++) {
        encode_bit((x >> i) & 1);
    }
}

void write3(const vector<int>& arr) {
    for (int i = 0; i < sz(arr); i += 29) {
        long cur = 0;
        for (int j = i; j < i + 29; j++) {
            cur *= 3;
            if (j < sz(arr)) {
                cur += arr[j];
            }
        }
        write(46, cur);
    }
}

const int maxn = 1005;

int dist[maxn], par[maxn];
bool vis[maxn];
static vector<int> graph[maxn];

void dfs(int u) {
    vis[u] = true;
    for (auto& v : graph[u]) {
        if (!vis[v]) {
            par[v] = u;
            dfs(v);
        }
    }
}

void encode(int n, int k, int m, int us[], int vs[]) {
    for (int i = 0; i < m; i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[i]);
    }
    dfs(0);
    for (int i = 1; i < n; i++) {
        write(10, par[i]);
    }
    auto bfs = [&](int src) -> void {
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        auto push = [&](int u, int d) -> void {
            if (dist[u] == -1) {
                dist[u] = d;
                q.push(u);
            }
        };
        push(src, 0);
        while (sz(q)) {
            int u = q.front();
            q.pop();
            for (auto& v : graph[u]) {
                push(v, dist[u] + 1);
            }
        }
    };
    vector<pair<int, int>> ans;
    vector<int> buf;
    for (int i = 0; i < k; i++) {
        bfs(i);
        for (int j = 1; j < n; j++) {
            buf.push_back(dist[par[j]] - dist[j] + 1);
        }}
    write3(buf);
}

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

int decode_bit();
void hops(int h, int c, int d);

long read(int bits) {
    long x = 0;
    for (int i = 0; i < bits; i++) {
        x |= long(decode_bit()) << i;
    }
    return x;
}

int read3() {
    static vector<int> buf;
    if (!sz(buf)) {
        long x = read(46);
        for (int i = 0; i < 29; i++) {
            buf.push_back(x % 3);
            x /= 3;
        }
    }
    int res = buf.back();
    buf.pop_back();
    return res;
}

const int maxn = 1005;

int base;
static vector<pair<int, int>> graph[maxn];

void dfs(int u, int d, int p = -1) {
    hops(base, u, d);
    for (auto& [v, w] : graph[u]) {
        if (v != p) {
            dfs(v, d + w, u);
        }
    }
}

void decode(int n, int k) {
    int par[n];
    for (int i = 1; i < n; i++) {
        par[i] = read(10);
    }
    for (int i = 0; i < k; i++) {
        for (auto& a : graph) {
            a.clear();
        }
        for (int j = 1; j < n; j++) {
            int w = read3() - 1;
            graph[j].emplace_back(par[j], w);
            graph[par[j]].emplace_back(j, -w);
        }
        base = i;
        dfs(i, 0);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10492 KB Output is correct - 67076 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 86 call(s) of encode_bit()
3 Correct 22 ms 5632 KB Output is correct - 60326 call(s) of encode_bit()
4 Correct 2 ms 4768 KB Output is correct - 86 call(s) of encode_bit()
5 Correct 28 ms 5708 KB Output is correct - 60326 call(s) of encode_bit()
6 Correct 28 ms 5944 KB Output is correct - 67076 call(s) of encode_bit()
7 Correct 45 ms 6228 KB Output is correct - 67076 call(s) of encode_bit()
8 Correct 22 ms 5688 KB Output is correct - 64432 call(s) of encode_bit()
9 Correct 22 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
10 Correct 27 ms 5728 KB Output is correct - 67076 call(s) of encode_bit()
11 Correct 27 ms 5784 KB Output is correct - 67076 call(s) of encode_bit()
12 Correct 26 ms 5684 KB Output is correct - 67076 call(s) of encode_bit()
13 Correct 46 ms 6416 KB Output is correct - 67076 call(s) of encode_bit()
14 Correct 26 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
15 Correct 25 ms 5740 KB Output is correct - 67076 call(s) of encode_bit()
16 Correct 47 ms 6196 KB Output is correct - 67076 call(s) of encode_bit()
17 Correct 46 ms 6216 KB Output is correct - 67076 call(s) of encode_bit()
18 Correct 48 ms 6472 KB Output is correct - 67076 call(s) of encode_bit()
19 Correct 32 ms 6004 KB Output is correct - 67076 call(s) of encode_bit()
20 Correct 77 ms 6688 KB Output is correct - 67076 call(s) of encode_bit()
21 Correct 64 ms 6876 KB Output is correct - 67076 call(s) of encode_bit()
22 Correct 49 ms 6336 KB Output is correct - 67076 call(s) of encode_bit()
23 Correct 68 ms 7008 KB Output is correct - 67076 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10492 KB Output is correct - 67076 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 86 call(s) of encode_bit()
3 Correct 22 ms 5632 KB Output is correct - 60326 call(s) of encode_bit()
4 Correct 2 ms 4768 KB Output is correct - 86 call(s) of encode_bit()
5 Correct 28 ms 5708 KB Output is correct - 60326 call(s) of encode_bit()
6 Correct 28 ms 5944 KB Output is correct - 67076 call(s) of encode_bit()
7 Correct 45 ms 6228 KB Output is correct - 67076 call(s) of encode_bit()
8 Correct 22 ms 5688 KB Output is correct - 64432 call(s) of encode_bit()
9 Correct 22 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
10 Correct 27 ms 5728 KB Output is correct - 67076 call(s) of encode_bit()
11 Correct 27 ms 5784 KB Output is correct - 67076 call(s) of encode_bit()
12 Correct 26 ms 5684 KB Output is correct - 67076 call(s) of encode_bit()
13 Correct 46 ms 6416 KB Output is correct - 67076 call(s) of encode_bit()
14 Correct 26 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
15 Correct 25 ms 5740 KB Output is correct - 67076 call(s) of encode_bit()
16 Correct 47 ms 6196 KB Output is correct - 67076 call(s) of encode_bit()
17 Correct 46 ms 6216 KB Output is correct - 67076 call(s) of encode_bit()
18 Correct 48 ms 6472 KB Output is correct - 67076 call(s) of encode_bit()
19 Correct 32 ms 6004 KB Output is correct - 67076 call(s) of encode_bit()
20 Correct 77 ms 6688 KB Output is correct - 67076 call(s) of encode_bit()
21 Correct 64 ms 6876 KB Output is correct - 67076 call(s) of encode_bit()
22 Correct 49 ms 6336 KB Output is correct - 67076 call(s) of encode_bit()
23 Correct 68 ms 7008 KB Output is correct - 67076 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10492 KB Output is correct - 67076 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 86 call(s) of encode_bit()
3 Correct 22 ms 5632 KB Output is correct - 60326 call(s) of encode_bit()
4 Correct 2 ms 4768 KB Output is correct - 86 call(s) of encode_bit()
5 Correct 28 ms 5708 KB Output is correct - 60326 call(s) of encode_bit()
6 Correct 28 ms 5944 KB Output is correct - 67076 call(s) of encode_bit()
7 Correct 45 ms 6228 KB Output is correct - 67076 call(s) of encode_bit()
8 Correct 22 ms 5688 KB Output is correct - 64432 call(s) of encode_bit()
9 Correct 22 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
10 Correct 27 ms 5728 KB Output is correct - 67076 call(s) of encode_bit()
11 Correct 27 ms 5784 KB Output is correct - 67076 call(s) of encode_bit()
12 Correct 26 ms 5684 KB Output is correct - 67076 call(s) of encode_bit()
13 Correct 46 ms 6416 KB Output is correct - 67076 call(s) of encode_bit()
14 Correct 26 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
15 Correct 25 ms 5740 KB Output is correct - 67076 call(s) of encode_bit()
16 Correct 47 ms 6196 KB Output is correct - 67076 call(s) of encode_bit()
17 Correct 46 ms 6216 KB Output is correct - 67076 call(s) of encode_bit()
18 Correct 48 ms 6472 KB Output is correct - 67076 call(s) of encode_bit()
19 Correct 32 ms 6004 KB Output is correct - 67076 call(s) of encode_bit()
20 Correct 77 ms 6688 KB Output is correct - 67076 call(s) of encode_bit()
21 Correct 64 ms 6876 KB Output is correct - 67076 call(s) of encode_bit()
22 Correct 49 ms 6336 KB Output is correct - 67076 call(s) of encode_bit()
23 Correct 68 ms 7008 KB Output is correct - 67076 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10492 KB Output is correct - 67076 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 86 call(s) of encode_bit()
3 Correct 22 ms 5632 KB Output is correct - 60326 call(s) of encode_bit()
4 Correct 2 ms 4768 KB Output is correct - 86 call(s) of encode_bit()
5 Correct 28 ms 5708 KB Output is correct - 60326 call(s) of encode_bit()
6 Correct 28 ms 5944 KB Output is correct - 67076 call(s) of encode_bit()
7 Correct 45 ms 6228 KB Output is correct - 67076 call(s) of encode_bit()
8 Correct 22 ms 5688 KB Output is correct - 64432 call(s) of encode_bit()
9 Correct 22 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
10 Correct 27 ms 5728 KB Output is correct - 67076 call(s) of encode_bit()
11 Correct 27 ms 5784 KB Output is correct - 67076 call(s) of encode_bit()
12 Correct 26 ms 5684 KB Output is correct - 67076 call(s) of encode_bit()
13 Correct 46 ms 6416 KB Output is correct - 67076 call(s) of encode_bit()
14 Correct 26 ms 5732 KB Output is correct - 67076 call(s) of encode_bit()
15 Correct 25 ms 5740 KB Output is correct - 67076 call(s) of encode_bit()
16 Correct 47 ms 6196 KB Output is correct - 67076 call(s) of encode_bit()
17 Correct 46 ms 6216 KB Output is correct - 67076 call(s) of encode_bit()
18 Correct 48 ms 6472 KB Output is correct - 67076 call(s) of encode_bit()
19 Correct 32 ms 6004 KB Output is correct - 67076 call(s) of encode_bit()
20 Correct 77 ms 6688 KB Output is correct - 67076 call(s) of encode_bit()
21 Correct 64 ms 6876 KB Output is correct - 67076 call(s) of encode_bit()
22 Correct 49 ms 6336 KB Output is correct - 67076 call(s) of encode_bit()
23 Correct 68 ms 7008 KB Output is correct - 67076 call(s) of encode_bit()