oj.uz

Submission #395052

# Submission time Handle Problem Language Result Execution time Memory
395052 2021-04-27T16:45:40 Z MarcoMeijer Saveit (IOI10_saveit) C++14
0 / 100
 328 ms 10724 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 writeSmallInt(int x, int bits) {
    RE(i,bits) {
        bool b = false;
        if(x & (1<<i)) b = 1;
        encode_bit(b);
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    // 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
            }
        }
    }

    // functions
    int curH = 0;
    function<void(int)> writeSpan = [&](int u) {
        FOR(v,chl[u]) {
            encode_bit(1);
            writeSmallInt(v,10);
            writeSpan(v);
        }
        encode_bit(0);
    };
    function<void(int)> writeDist = [&](int u) {
        if(parent[u] != -1)
            writeSmallInt(dist[curH][parent[u]] - dist[curH][u] + 1, 2);
        FOR(v,chl[u]) writeDist(v);
    };

    // calling the above functions
    writeSpan(0);
    REP(h,1,nh) {
        curH = h;
        writeDist(0);
    }
}

#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

int readSmallInt(int bits) {
    int res = 0;
    RE(i,bits) {
        bool b = decode_bit();
        if(b) res |= (1<<i);
    }
    return res;
}

void decode(int nv, int nh) {
    // 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));

    // functions
    int curH = 0;
    function<void(int)> readSpan = [&](int u) {
        while(true) {
            bool b = decode_bit();
            if(!b) return;
            int v = readSmallInt(10);
            chl[u].pb(v);
            readSpan(v);
        }
    };
    function<void(int)> readDist = [&](int u) {
        if(parent[u] != -1) {
            int dif = readSmallInt(2) - 1;
            dist[curH][u] = dist[curH][parent[u]] + dif;
        }
        FOR(v,chl[u]) readDist(v);
    };

    // calling the above functions
    readSpan(0);
    REP(h,1,nh) {
        curH = h;
        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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 10724 KB Output isn't correct
2 Incorrect 3 ms 4584 KB Output isn't correct
3 Incorrect 31 ms 5544 KB Output isn't correct
4 Incorrect 3 ms 4584 KB Output isn't correct
5 Incorrect 35 ms 5748 KB Output isn't correct
6 Incorrect 44 ms 5816 KB Output isn't correct
7 Incorrect 54 ms 6156 KB Output isn't correct
8 Incorrect 27 ms 5716 KB Output isn't correct
9 Incorrect 30 ms 5668 KB Output isn't correct
10 Incorrect 30 ms 5668 KB Output isn't correct
11 Incorrect 39 ms 5856 KB Output isn't correct
12 Incorrect 28 ms 5716 KB Output isn't correct
13 Incorrect 65 ms 6308 KB Output isn't correct
14 Incorrect 35 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 5768 KB Output isn't correct
16 Incorrect 65 ms 6292 KB Output isn't correct
17 Incorrect 55 ms 6216 KB Output isn't correct
18 Incorrect 74 ms 6528 KB Output isn't correct
19 Incorrect 51 ms 6120 KB Output isn't correct
20 Incorrect 80 ms 6716 KB Output isn't correct
21 Incorrect 94 ms 6784 KB Output isn't correct
22 Incorrect 69 ms 6296 KB Output isn't correct
23 Incorrect 97 ms 7088 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 10724 KB Output isn't correct
2 Incorrect 3 ms 4584 KB Output isn't correct
3 Incorrect 31 ms 5544 KB Output isn't correct
4 Incorrect 3 ms 4584 KB Output isn't correct
5 Incorrect 35 ms 5748 KB Output isn't correct
6 Incorrect 44 ms 5816 KB Output isn't correct
7 Incorrect 54 ms 6156 KB Output isn't correct
8 Incorrect 27 ms 5716 KB Output isn't correct
9 Incorrect 30 ms 5668 KB Output isn't correct
10 Incorrect 30 ms 5668 KB Output isn't correct
11 Incorrect 39 ms 5856 KB Output isn't correct
12 Incorrect 28 ms 5716 KB Output isn't correct
13 Incorrect 65 ms 6308 KB Output isn't correct
14 Incorrect 35 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 5768 KB Output isn't correct
16 Incorrect 65 ms 6292 KB Output isn't correct
17 Incorrect 55 ms 6216 KB Output isn't correct
18 Incorrect 74 ms 6528 KB Output isn't correct
19 Incorrect 51 ms 6120 KB Output isn't correct
20 Incorrect 80 ms 6716 KB Output isn't correct
21 Incorrect 94 ms 6784 KB Output isn't correct
22 Incorrect 69 ms 6296 KB Output isn't correct
23 Incorrect 97 ms 7088 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 10724 KB Output isn't correct
2 Incorrect 3 ms 4584 KB Output isn't correct
3 Incorrect 31 ms 5544 KB Output isn't correct
4 Incorrect 3 ms 4584 KB Output isn't correct
5 Incorrect 35 ms 5748 KB Output isn't correct
6 Incorrect 44 ms 5816 KB Output isn't correct
7 Incorrect 54 ms 6156 KB Output isn't correct
8 Incorrect 27 ms 5716 KB Output isn't correct
9 Incorrect 30 ms 5668 KB Output isn't correct
10 Incorrect 30 ms 5668 KB Output isn't correct
11 Incorrect 39 ms 5856 KB Output isn't correct
12 Incorrect 28 ms 5716 KB Output isn't correct
13 Incorrect 65 ms 6308 KB Output isn't correct
14 Incorrect 35 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 5768 KB Output isn't correct
16 Incorrect 65 ms 6292 KB Output isn't correct
17 Incorrect 55 ms 6216 KB Output isn't correct
18 Incorrect 74 ms 6528 KB Output isn't correct
19 Incorrect 51 ms 6120 KB Output isn't correct
20 Incorrect 80 ms 6716 KB Output isn't correct
21 Incorrect 94 ms 6784 KB Output isn't correct
22 Incorrect 69 ms 6296 KB Output isn't correct
23 Incorrect 97 ms 7088 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 10724 KB Output isn't correct
2 Incorrect 3 ms 4584 KB Output isn't correct
3 Incorrect 31 ms 5544 KB Output isn't correct
4 Incorrect 3 ms 4584 KB Output isn't correct
5 Incorrect 35 ms 5748 KB Output isn't correct
6 Incorrect 44 ms 5816 KB Output isn't correct
7 Incorrect 54 ms 6156 KB Output isn't correct
8 Incorrect 27 ms 5716 KB Output isn't correct
9 Incorrect 30 ms 5668 KB Output isn't correct
10 Incorrect 30 ms 5668 KB Output isn't correct
11 Incorrect 39 ms 5856 KB Output isn't correct
12 Incorrect 28 ms 5716 KB Output isn't correct
13 Incorrect 65 ms 6308 KB Output isn't correct
14 Incorrect 35 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 5768 KB Output isn't correct
16 Incorrect 65 ms 6292 KB Output isn't correct
17 Incorrect 55 ms 6216 KB Output isn't correct
18 Incorrect 74 ms 6528 KB Output isn't correct
19 Incorrect 51 ms 6120 KB Output isn't correct
20 Incorrect 80 ms 6716 KB Output isn't correct
21 Incorrect 94 ms 6784 KB Output isn't correct
22 Incorrect 69 ms 6296 KB Output isn't correct
23 Incorrect 97 ms 7088 KB Output isn't correct