oj.uz

Submission #395072

# Submission time Handle Problem Language Result Execution time Memory
395072 2021-04-27T17:11:02 Z MarcoMeijer Saveit (IOI10_saveit) C++14
100 / 100
 365 ms 10520 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    // write functions
    vi ternStack;
    auto writeSmallInt      = [](int x, int bits) {
        RE(i,bits) {
            bool b = false;
            if(x & (1<<i)) b = 1;
            encode_bit(b);
        }
    };
    auto finishTransmission = [&]() {
        while(ternStack.size() < 3) ternStack.push_back(0);
        int res = 0;
        FOR(u,ternStack) res = res*3 + u;
        writeSmallInt(res,5);
        ternStack.clear();
    };
    auto writeTernary       = [&](int x) {
        ternStack.pb(x);
        if(ternStack.size() == 3)
            finishTransmission();
    };

    // create original graph
    vector<vi> adj; adj.resize(nv);
    RE(i,ne) {
        adj[v1[i]].pb(v2[i]);
        adj[v2[i]].pb(v1[i]);
    }

    // spanning tree
    vector<vi> chl; chl.resize(nv);
    vi parent; parent.assign(nv, -1);

    // fill dist
    vector<vi> dist; dist.resize(nh);
    RE(h,nh) {
        dist[h].assign(nv,-1);
        queue<int> q;
        q.push(h); dist[h][h] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            FOR(v,adj[u]) {
                if(dist[h][v] != -1) continue;
                dist[h][v] = dist[h][u] + 1;
                q.push(v);
                if(h == 0) chl[u].pb(v), parent[v] = u; // create spanning tree
            }
        }
    }

    // write the spanning tree
    REP(u,1,nv) writeSmallInt(parent[u],10);
    RE(u,nv) sort(all(chl[u]));

    // writing the distances
    REP(h,1,nh) {
        function<void(int)> writeDist = [&](int u) {
            if(parent[u] != -1)
                writeTernary(dist[h][u] - dist[h][parent[u]] + 1);
            FOR(v,chl[u]) writeDist(v);
        };
        writeDist(0);
    }
    finishTransmission();
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second

void decode(int nv, int nh) {
    // read function
    vi ternStack;
    auto readSmallInt = [](int bits) {
        int res = 0;
        RE(i,bits) {
            bool b = decode_bit();
            if(b) res |= (1<<i);
        }
        return res;
    };
    auto readTernary = [&]() {
        if(ternStack.empty()) {
            int x = readSmallInt(5);
            RE(_,3) {
                ternStack.pb(x%3);
                x /= 3;
            }
        }
        int res = ternStack.back(); ternStack.pop_back();
        return res;
    };

    // spanning tree
    vector<vi> chl; chl.resize(nv);
    vi parent; parent.assign(nv, -1);
    
    // distance array
    vector<vi> dist; dist.assign(nh, vi(nv,0));

    // read the spanning tree
    REP(u,1,nv) {
        parent[u] = readSmallInt(10);
        chl[parent[u]].pb(u);
    }
    function<void(int)> dfsDist = [&](int u) {
        FOR(v,chl[u]) {
            dist[0][v] = dist[0][u] + 1;
            dfsDist(v);
        }
    };
    dfsDist(0);

    // reading the distances
    REP(h,1,nh) {
        function<void(int)> readDist = [&](int u) {
            if(parent[u] != -1) {
                int dif = readTernary() - 1;
                dist[h][u] = dist[h][parent[u]] + dif;
            }
            FOR(v,chl[u]) readDist(v);
        };
        readDist(0);
        int delta = -dist[h][h];
        RE(u,nv) dist[h][u] += delta;
    }

    // returning the answer
    RE(i,nh) RE(j,nv) hops(i,j,dist[i][j]);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 10520 KB Output is correct - 68270 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 55 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is correct - 61435 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 70 call(s) of encode_bit()
5 Correct 31 ms 5668 KB Output is correct - 61435 call(s) of encode_bit()
6 Correct 32 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
7 Correct 49 ms 6040 KB Output is correct - 68270 call(s) of encode_bit()
8 Correct 32 ms 5596 KB Output is correct - 65605 call(s) of encode_bit()
9 Correct 31 ms 5784 KB Output is correct - 68270 call(s) of encode_bit()
10 Correct 31 ms 5712 KB Output is correct - 68270 call(s) of encode_bit()
11 Correct 37 ms 5796 KB Output is correct - 68270 call(s) of encode_bit()
12 Correct 31 ms 5724 KB Output is correct - 68270 call(s) of encode_bit()
13 Correct 62 ms 6304 KB Output is correct - 68270 call(s) of encode_bit()
14 Correct 31 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
15 Correct 31 ms 5844 KB Output is correct - 68270 call(s) of encode_bit()
16 Correct 57 ms 6228 KB Output is correct - 68270 call(s) of encode_bit()
17 Correct 59 ms 6220 KB Output is correct - 68270 call(s) of encode_bit()
18 Correct 62 ms 6512 KB Output is correct - 68270 call(s) of encode_bit()
19 Correct 46 ms 5948 KB Output is correct - 68270 call(s) of encode_bit()
20 Correct 91 ms 6608 KB Output is correct - 68270 call(s) of encode_bit()
21 Correct 79 ms 6684 KB Output is correct - 68270 call(s) of encode_bit()
22 Correct 69 ms 6224 KB Output is correct - 68270 call(s) of encode_bit()
23 Correct 89 ms 6908 KB Output is correct - 68270 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 10520 KB Output is correct - 68270 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 55 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is correct - 61435 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 70 call(s) of encode_bit()
5 Correct 31 ms 5668 KB Output is correct - 61435 call(s) of encode_bit()
6 Correct 32 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
7 Correct 49 ms 6040 KB Output is correct - 68270 call(s) of encode_bit()
8 Correct 32 ms 5596 KB Output is correct - 65605 call(s) of encode_bit()
9 Correct 31 ms 5784 KB Output is correct - 68270 call(s) of encode_bit()
10 Correct 31 ms 5712 KB Output is correct - 68270 call(s) of encode_bit()
11 Correct 37 ms 5796 KB Output is correct - 68270 call(s) of encode_bit()
12 Correct 31 ms 5724 KB Output is correct - 68270 call(s) of encode_bit()
13 Correct 62 ms 6304 KB Output is correct - 68270 call(s) of encode_bit()
14 Correct 31 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
15 Correct 31 ms 5844 KB Output is correct - 68270 call(s) of encode_bit()
16 Correct 57 ms 6228 KB Output is correct - 68270 call(s) of encode_bit()
17 Correct 59 ms 6220 KB Output is correct - 68270 call(s) of encode_bit()
18 Correct 62 ms 6512 KB Output is correct - 68270 call(s) of encode_bit()
19 Correct 46 ms 5948 KB Output is correct - 68270 call(s) of encode_bit()
20 Correct 91 ms 6608 KB Output is correct - 68270 call(s) of encode_bit()
21 Correct 79 ms 6684 KB Output is correct - 68270 call(s) of encode_bit()
22 Correct 69 ms 6224 KB Output is correct - 68270 call(s) of encode_bit()
23 Correct 89 ms 6908 KB Output is correct - 68270 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 10520 KB Output is correct - 68270 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 55 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is correct - 61435 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 70 call(s) of encode_bit()
5 Correct 31 ms 5668 KB Output is correct - 61435 call(s) of encode_bit()
6 Correct 32 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
7 Correct 49 ms 6040 KB Output is correct - 68270 call(s) of encode_bit()
8 Correct 32 ms 5596 KB Output is correct - 65605 call(s) of encode_bit()
9 Correct 31 ms 5784 KB Output is correct - 68270 call(s) of encode_bit()
10 Correct 31 ms 5712 KB Output is correct - 68270 call(s) of encode_bit()
11 Correct 37 ms 5796 KB Output is correct - 68270 call(s) of encode_bit()
12 Correct 31 ms 5724 KB Output is correct - 68270 call(s) of encode_bit()
13 Correct 62 ms 6304 KB Output is correct - 68270 call(s) of encode_bit()
14 Correct 31 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
15 Correct 31 ms 5844 KB Output is correct - 68270 call(s) of encode_bit()
16 Correct 57 ms 6228 KB Output is correct - 68270 call(s) of encode_bit()
17 Correct 59 ms 6220 KB Output is correct - 68270 call(s) of encode_bit()
18 Correct 62 ms 6512 KB Output is correct - 68270 call(s) of encode_bit()
19 Correct 46 ms 5948 KB Output is correct - 68270 call(s) of encode_bit()
20 Correct 91 ms 6608 KB Output is correct - 68270 call(s) of encode_bit()
21 Correct 79 ms 6684 KB Output is correct - 68270 call(s) of encode_bit()
22 Correct 69 ms 6224 KB Output is correct - 68270 call(s) of encode_bit()
23 Correct 89 ms 6908 KB Output is correct - 68270 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 10520 KB Output is correct - 68270 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 55 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is correct - 61435 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 70 call(s) of encode_bit()
5 Correct 31 ms 5668 KB Output is correct - 61435 call(s) of encode_bit()
6 Correct 32 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
7 Correct 49 ms 6040 KB Output is correct - 68270 call(s) of encode_bit()
8 Correct 32 ms 5596 KB Output is correct - 65605 call(s) of encode_bit()
9 Correct 31 ms 5784 KB Output is correct - 68270 call(s) of encode_bit()
10 Correct 31 ms 5712 KB Output is correct - 68270 call(s) of encode_bit()
11 Correct 37 ms 5796 KB Output is correct - 68270 call(s) of encode_bit()
12 Correct 31 ms 5724 KB Output is correct - 68270 call(s) of encode_bit()
13 Correct 62 ms 6304 KB Output is correct - 68270 call(s) of encode_bit()
14 Correct 31 ms 5716 KB Output is correct - 68270 call(s) of encode_bit()
15 Correct 31 ms 5844 KB Output is correct - 68270 call(s) of encode_bit()
16 Correct 57 ms 6228 KB Output is correct - 68270 call(s) of encode_bit()
17 Correct 59 ms 6220 KB Output is correct - 68270 call(s) of encode_bit()
18 Correct 62 ms 6512 KB Output is correct - 68270 call(s) of encode_bit()
19 Correct 46 ms 5948 KB Output is correct - 68270 call(s) of encode_bit()
20 Correct 91 ms 6608 KB Output is correct - 68270 call(s) of encode_bit()
21 Correct 79 ms 6684 KB Output is correct - 68270 call(s) of encode_bit()
22 Correct 69 ms 6224 KB Output is correct - 68270 call(s) of encode_bit()
23 Correct 89 ms 6908 KB Output is correct - 68270 call(s) of encode_bit()