oj.uz

Submission #982629

# Submission time Handle Problem Language Result Execution time Memory
982629 2024-05-14T14:20:19 Z Sharky Saveit (IOI10_saveit) C++17
100 / 100
 198 ms 21664 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

namespace Encoder {
    const int inf = 6969;
    int p[1001];
    vector<int> adj[1001], g[1001];
    int dsu[1001], rt[1001];
    bool vis[1001];
    int find(int u) {
        return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
    }
    void merge(int u, int v) {
        dsu[find(v)] = find(u);
    }
    void dfs(int u, int fa, int dist) {
        p[u] = fa;
        // if (u == 1) cout << u << " " << dist << '\n';
        for (int v : adj[u]) if (v != fa) dfs(v, u, dist + 1);
    }
    void dfs2(int u) {
        vis[u] = 1;
        for (int v : g[u]) if (rt[u] + 1 == rt[v] && !vis[v]) {
            adj[u].push_back(v);
            adj[v].push_back(u);
            dfs2(v);
        }
    }
};

using namespace Encoder;

void encode(int n, int h, int m, int *uu, int *vv){
    for (int i = 0; i < n; i++) dsu[i] = i;
    for (int i = 0; i < m; i++) {
        g[uu[i]].push_back(vv[i]);
        g[vv[i]].push_back(uu[i]);
    }
    queue<int> q;
    q.push(0);
    for (int i = 0; i < n; i++) rt[i] = inf;
    rt[0] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) if (rt[v] > rt[u] + 1) {
            rt[v] = rt[u] + 1;
            q.push(v);
        }
    }
    // cout << rt[1] << '\n';
    dfs2(0);
    dfs(0, -1, 0);
    // for (int i = 0; i < n; i++) cout << p[i] << ' ';
    // cout << '\n';
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            int bit = !!(p[i] & (1 << j));
            encode_bit(bit);
            // cout << "e " << bit << '\n';
        }
    }
    queue<int> bfs;
    vector<int> vt;
    for (int s = 0; s < h; s++) {
        bfs.push(s);
        vector<int> di(n, inf);
        di[s] = 0;
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (int v : g[u]) if (di[v] > di[u] + 1) {
                di[v] = di[u] + 1;
                bfs.push(v);
            }
        }
        for (int i = 1; i < n; i++) {
            int delta = di[i] - di[p[i]];
            vt.push_back(delta + 1);
        }
        // if (s == 1) cout << di[0] << ' ' << di[2] << '\n';
    }
    int sz = vt.size();
    while (sz % 3) {
        vt.push_back(0);
        sz++;
    }
    // cout << "encoding\n";
    // for (auto i : vt) cout << i - 1 << ' ';
    // cout << "\n";
    for (int i = 0; i + 2 < sz; i += 3) {
        int x = vt[i] * 9 + vt[i + 1] * 3 + vt[i + 2];
        vector<int> bit;
        while (x) {
            bit.push_back(x % 2);
            x /= 2;
        }
        while ((int) bit.size() < 5) bit.push_back(0);
        reverse(bit.begin(), bit.end());
        for (int e : bit) {
            // cout << "e " << e << '\n';
            encode_bit(e);
        }
    }
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

namespace Decoder {
    int p[1001], d[37], di[1001][1001];
    vector<int> adj[1001], topo;
    void dfs(int u, int fa, int h, int distance) {
        // if (u == 1) cout << u << ' ' << distance << '\n';
        di[u][0] = di[0][u] = distance;
        for (int v : adj[u]) if (v != fa) dfs(v, u, h, distance + 1);
        if (u) topo.push_back(u);
    }
};

using namespace Decoder;

void decode(int n, int h) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) p[i] += (decode_bit() * (1 << j));
        // cout << p[i] << ' ';
        adj[p[i]].push_back(i);
    }
    // cout << '\n';
    vector<vector<int>> w(h, vector<int> (n, 0));
    dfs(0, -1, h, 0);
    reverse(topo.begin(), topo.end());
    int waves = (h * (n - 1) + 2) / 3;
    // cout << "# bits " << waves * 5 << '\n';
    int hub = 0, city = 1;
    while (waves--) {
        // cout << "hi\n";
        vector<int> bit;
        for (int i = 0; i < 5; i++) bit.push_back(decode_bit());
        int hash = 0;
        for (int i = 0; i < 5; i++) hash = hash * 2 + bit[i];
        vector<int> v(3);
        v[0] = hash / 9;
        hash -= v[0] * 9;
        v[1] = hash / 3;
        hash -= v[1] * 3;
        v[2] = hash;
        for (int i = 0; i < 3; i++) {
            if (hub >= h) break;
            w[hub][city] = v[i] - 1;
            // cout << hub << ' ' << p[city] << ' ' << city << ' ' << v[i] - 1 << '\n';
            city++; if (city == n) city = 1, hub++;
        }
    }
    // cout << "topo\n";
    // for (int j : topo) cout << j << ' ';
    // cout << '\n';
    for (int i = 0; i < h; i++) for (int j : topo) {
        di[i][j] = di[i][p[j]] + w[i][j];
        // if (i == 1 && j == 1) cout << i << ' ' << p[j] << ' ' << di[i][p[j]] << ' ' << w[i][j] << '\n';
    }
    for (int i = 0; i < h; i++) for (int j = 0; j < n; j++) {
        // cout << i << ' ' << j << ' ' << di[i][j] << '\n';
        hops(i, j, di[i][j]);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 21664 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 13316 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 19 ms 15976 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 13316 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 26 ms 16248 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 23 ms 17056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 34 ms 16972 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 16396 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 20 ms 16480 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 20 ms 16696 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 25 ms 16880 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 16488 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 54 ms 17376 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 48 ms 17060 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 34 ms 17324 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 42 ms 17440 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 31 ms 16712 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 51 ms 19376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 64 ms 19896 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 49 ms 17088 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 54 ms 20136 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 21664 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 13316 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 19 ms 15976 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 13316 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 26 ms 16248 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 23 ms 17056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 34 ms 16972 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 16396 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 20 ms 16480 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 20 ms 16696 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 25 ms 16880 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 16488 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 54 ms 17376 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 48 ms 17060 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 34 ms 17324 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 42 ms 17440 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 31 ms 16712 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 51 ms 19376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 64 ms 19896 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 49 ms 17088 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 54 ms 20136 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 21664 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 13316 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 19 ms 15976 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 13316 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 26 ms 16248 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 23 ms 17056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 34 ms 16972 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 16396 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 20 ms 16480 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 20 ms 16696 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 25 ms 16880 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 16488 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 54 ms 17376 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 48 ms 17060 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 34 ms 17324 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 42 ms 17440 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 31 ms 16712 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 51 ms 19376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 64 ms 19896 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 49 ms 17088 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 54 ms 20136 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 21664 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 13316 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 19 ms 15976 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 13316 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 26 ms 16248 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 23 ms 17056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 34 ms 16972 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 16396 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 20 ms 16480 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 20 ms 16696 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 25 ms 16880 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 16488 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 54 ms 17376 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 16496 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 48 ms 17060 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 34 ms 17324 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 42 ms 17440 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 31 ms 16712 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 51 ms 19376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 64 ms 19896 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 49 ms 17088 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 54 ms 20136 KB Output is correct - 69930 call(s) of encode_bit()