oj.uz

Submission #596777

# Submission time Handle Problem Language Result Execution time Memory
596777 2022-07-15T04:22:33 Z skittles1412 Saveit (IOI10_saveit) C++17
50 / 100
 427 ms 12896 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, int x) {
    for (int i = 0; i < bits; i++) {
        encode_bit((x >> i) & 1);
    }
}

void encode(int n, int k, int m, int us[], int vs[]) {
    int dist[1024];
    vector<int> graph[n];
    for (int i = 0; i < m; i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[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;
    for (int i = 0; i < k; i++) {
        bfs(i);
        bool vis[n] {};
        for (auto [u, v] : ans) {
            if (abs(dist[u] - dist[v]) == 1) {
                if (dist[u] > dist[v]) {
                    swap(u, v);
                }
                vis[v] = true;
            }
        }
        for (int j = 0; j < m; j++) {
            int u = us[j], v = vs[j];
            if (abs(dist[u] - dist[v]) == 1) {
                if (dist[u] > dist[v]) {
                    swap(u, v);
                }
                if (!vis[v]) {
                    ans.emplace_back(u, v);
                    vis[v] = true;
                }
            }
        }
    }
    for (auto& [u, v] : ans) {
        write(10, u);
        write(10, v);
    }
    write(10, 1023);
}

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

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

void decode(int n, int k) {
    int dist[1024];
    vector<int> graph[n];
    while (true) {
        int u = read(10);
        if (u == 1023) {
            break;
        }
        int v = read(10);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    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);
            }
        }
    };
    for (int i = 0; i < k; i++) {
        bfs(i);
        for (int j = 0; j < n; j++) {
            hops(i, j, dist[j]);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 12896 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 5456 KB Output is correct - 69210 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 48 ms 6344 KB Output is partially correct - 153990 call(s) of encode_bit()
6 Correct 55 ms 6412 KB Output is partially correct - 155930 call(s) of encode_bit()
7 Correct 93 ms 8000 KB Output is partially correct - 297330 call(s) of encode_bit()
8 Correct 18 ms 5020 KB Output is correct - 33870 call(s) of encode_bit()
9 Correct 20 ms 5212 KB Output is correct - 32570 call(s) of encode_bit()
10 Correct 18 ms 5244 KB Output is correct - 31790 call(s) of encode_bit()
11 Correct 39 ms 5528 KB Output is correct - 64370 call(s) of encode_bit()
12 Correct 16 ms 5004 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 69 ms 7196 KB Output is partially correct - 183830 call(s) of encode_bit()
14 Correct 20 ms 5244 KB Output is correct - 41110 call(s) of encode_bit()
15 Correct 22 ms 5372 KB Output is correct - 43410 call(s) of encode_bit()
16 Correct 70 ms 6240 KB Output is partially correct - 93070 call(s) of encode_bit()
17 Correct 65 ms 6048 KB Output is partially correct - 83130 call(s) of encode_bit()
18 Correct 62 ms 6680 KB Output is partially correct - 125190 call(s) of encode_bit()
19 Correct 70 ms 6196 KB Output is partially correct - 127110 call(s) of encode_bit()
20 Correct 94 ms 7356 KB Output is partially correct - 165550 call(s) of encode_bit()
21 Correct 92 ms 7524 KB Output is partially correct - 170410 call(s) of encode_bit()
22 Correct 99 ms 7936 KB Output is partially correct - 256290 call(s) of encode_bit()
23 Correct 117 ms 8464 KB Output is partially correct - 239030 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 12896 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 5456 KB Output is correct - 69210 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 48 ms 6344 KB Output is partially correct - 153990 call(s) of encode_bit()
6 Correct 55 ms 6412 KB Output is partially correct - 155930 call(s) of encode_bit()
7 Correct 93 ms 8000 KB Output is partially correct - 297330 call(s) of encode_bit()
8 Correct 18 ms 5020 KB Output is correct - 33870 call(s) of encode_bit()
9 Correct 20 ms 5212 KB Output is correct - 32570 call(s) of encode_bit()
10 Correct 18 ms 5244 KB Output is correct - 31790 call(s) of encode_bit()
11 Correct 39 ms 5528 KB Output is correct - 64370 call(s) of encode_bit()
12 Correct 16 ms 5004 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 69 ms 7196 KB Output is partially correct - 183830 call(s) of encode_bit()
14 Correct 20 ms 5244 KB Output is correct - 41110 call(s) of encode_bit()
15 Correct 22 ms 5372 KB Output is correct - 43410 call(s) of encode_bit()
16 Correct 70 ms 6240 KB Output is partially correct - 93070 call(s) of encode_bit()
17 Correct 65 ms 6048 KB Output is partially correct - 83130 call(s) of encode_bit()
18 Correct 62 ms 6680 KB Output is partially correct - 125190 call(s) of encode_bit()
19 Correct 70 ms 6196 KB Output is partially correct - 127110 call(s) of encode_bit()
20 Correct 94 ms 7356 KB Output is partially correct - 165550 call(s) of encode_bit()
21 Correct 92 ms 7524 KB Output is partially correct - 170410 call(s) of encode_bit()
22 Correct 99 ms 7936 KB Output is partially correct - 256290 call(s) of encode_bit()
23 Correct 117 ms 8464 KB Output is partially correct - 239030 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 12896 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 5456 KB Output is correct - 69210 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 48 ms 6344 KB Output is partially correct - 153990 call(s) of encode_bit()
6 Correct 55 ms 6412 KB Output is partially correct - 155930 call(s) of encode_bit()
7 Correct 93 ms 8000 KB Output is partially correct - 297330 call(s) of encode_bit()
8 Correct 18 ms 5020 KB Output is correct - 33870 call(s) of encode_bit()
9 Correct 20 ms 5212 KB Output is correct - 32570 call(s) of encode_bit()
10 Correct 18 ms 5244 KB Output is correct - 31790 call(s) of encode_bit()
11 Correct 39 ms 5528 KB Output is correct - 64370 call(s) of encode_bit()
12 Correct 16 ms 5004 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 69 ms 7196 KB Output is partially correct - 183830 call(s) of encode_bit()
14 Correct 20 ms 5244 KB Output is correct - 41110 call(s) of encode_bit()
15 Correct 22 ms 5372 KB Output is correct - 43410 call(s) of encode_bit()
16 Correct 70 ms 6240 KB Output is partially correct - 93070 call(s) of encode_bit()
17 Correct 65 ms 6048 KB Output is partially correct - 83130 call(s) of encode_bit()
18 Correct 62 ms 6680 KB Output is partially correct - 125190 call(s) of encode_bit()
19 Correct 70 ms 6196 KB Output is partially correct - 127110 call(s) of encode_bit()
20 Correct 94 ms 7356 KB Output is partially correct - 165550 call(s) of encode_bit()
21 Correct 92 ms 7524 KB Output is partially correct - 170410 call(s) of encode_bit()
22 Correct 99 ms 7936 KB Output is partially correct - 256290 call(s) of encode_bit()
23 Correct 117 ms 8464 KB Output is partially correct - 239030 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 12896 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 5456 KB Output is correct - 69210 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 48 ms 6344 KB Output is partially correct - 153990 call(s) of encode_bit()
6 Correct 55 ms 6412 KB Output is partially correct - 155930 call(s) of encode_bit()
7 Correct 93 ms 8000 KB Output is partially correct - 297330 call(s) of encode_bit()
8 Correct 18 ms 5020 KB Output is correct - 33870 call(s) of encode_bit()
9 Correct 20 ms 5212 KB Output is correct - 32570 call(s) of encode_bit()
10 Correct 18 ms 5244 KB Output is correct - 31790 call(s) of encode_bit()
11 Correct 39 ms 5528 KB Output is correct - 64370 call(s) of encode_bit()
12 Correct 16 ms 5004 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 69 ms 7196 KB Output is partially correct - 183830 call(s) of encode_bit()
14 Correct 20 ms 5244 KB Output is correct - 41110 call(s) of encode_bit()
15 Correct 22 ms 5372 KB Output is correct - 43410 call(s) of encode_bit()
16 Correct 70 ms 6240 KB Output is partially correct - 93070 call(s) of encode_bit()
17 Correct 65 ms 6048 KB Output is partially correct - 83130 call(s) of encode_bit()
18 Correct 62 ms 6680 KB Output is partially correct - 125190 call(s) of encode_bit()
19 Correct 70 ms 6196 KB Output is partially correct - 127110 call(s) of encode_bit()
20 Correct 94 ms 7356 KB Output is partially correct - 165550 call(s) of encode_bit()
21 Correct 92 ms 7524 KB Output is partially correct - 170410 call(s) of encode_bit()
22 Correct 99 ms 7936 KB Output is partially correct - 256290 call(s) of encode_bit()
23 Correct 117 ms 8464 KB Output is partially correct - 239030 call(s) of encode_bit()