oj.uz

Submission #395060

# Submission time Handle Problem Language Result Execution time Memory
395060 2021-04-27T16:54:57 Z MarcoMeijer Saveit (IOI10_saveit) C++14
0 / 100
 269 ms 10492 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
            }
        }
    }

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

    // writing the distances
    REP(h,1,nh) {
        function<void(int)> writeDist = [&](int u) {
            if(parent[u] != -1)
                writeSmallInt(dist[h][u] - dist[h][parent[u]] + 1, 2);
            FOR(v,chl[u]) writeDist(v);
        };
        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));

    // 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 = readSmallInt(2) - 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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 10492 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5612 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 32 ms 5748 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 33 ms 5972 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 55 ms 6136 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Incorrect 27 ms 5704 KB wrong parameter
9 Incorrect 28 ms 5716 KB wrong parameter
10 Incorrect 30 ms 5716 KB wrong parameter
11 Incorrect 33 ms 5844 KB wrong parameter
12 Correct 30 ms 5836 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Incorrect 71 ms 6300 KB wrong parameter
14 Incorrect 27 ms 5924 KB wrong parameter
15 Incorrect 31 ms 5796 KB wrong parameter
16 Incorrect 54 ms 6168 KB wrong parameter
17 Incorrect 61 ms 6268 KB wrong parameter
18 Incorrect 55 ms 6400 KB wrong parameter
19 Incorrect 41 ms 6008 KB wrong parameter
20 Incorrect 87 ms 6744 KB wrong parameter
21 Incorrect 96 ms 6792 KB wrong parameter
22 Incorrect 68 ms 6384 KB wrong parameter
23 Incorrect 82 ms 7064 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 10492 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5612 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 32 ms 5748 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 33 ms 5972 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 55 ms 6136 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Incorrect 27 ms 5704 KB wrong parameter
9 Incorrect 28 ms 5716 KB wrong parameter
10 Incorrect 30 ms 5716 KB wrong parameter
11 Incorrect 33 ms 5844 KB wrong parameter
12 Correct 30 ms 5836 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Incorrect 71 ms 6300 KB wrong parameter
14 Incorrect 27 ms 5924 KB wrong parameter
15 Incorrect 31 ms 5796 KB wrong parameter
16 Incorrect 54 ms 6168 KB wrong parameter
17 Incorrect 61 ms 6268 KB wrong parameter
18 Incorrect 55 ms 6400 KB wrong parameter
19 Incorrect 41 ms 6008 KB wrong parameter
20 Incorrect 87 ms 6744 KB wrong parameter
21 Incorrect 96 ms 6792 KB wrong parameter
22 Incorrect 68 ms 6384 KB wrong parameter
23 Incorrect 82 ms 7064 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 10492 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5612 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 32 ms 5748 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 33 ms 5972 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 55 ms 6136 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Incorrect 27 ms 5704 KB wrong parameter
9 Incorrect 28 ms 5716 KB wrong parameter
10 Incorrect 30 ms 5716 KB wrong parameter
11 Incorrect 33 ms 5844 KB wrong parameter
12 Correct 30 ms 5836 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Incorrect 71 ms 6300 KB wrong parameter
14 Incorrect 27 ms 5924 KB wrong parameter
15 Incorrect 31 ms 5796 KB wrong parameter
16 Incorrect 54 ms 6168 KB wrong parameter
17 Incorrect 61 ms 6268 KB wrong parameter
18 Incorrect 55 ms 6400 KB wrong parameter
19 Incorrect 41 ms 6008 KB wrong parameter
20 Incorrect 87 ms 6744 KB wrong parameter
21 Incorrect 96 ms 6792 KB wrong parameter
22 Incorrect 68 ms 6384 KB wrong parameter
23 Incorrect 82 ms 7064 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 10492 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5612 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 3 ms 4584 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 32 ms 5748 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 33 ms 5972 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 55 ms 6136 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Incorrect 27 ms 5704 KB wrong parameter
9 Incorrect 28 ms 5716 KB wrong parameter
10 Incorrect 30 ms 5716 KB wrong parameter
11 Incorrect 33 ms 5844 KB wrong parameter
12 Correct 30 ms 5836 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Incorrect 71 ms 6300 KB wrong parameter
14 Incorrect 27 ms 5924 KB wrong parameter
15 Incorrect 31 ms 5796 KB wrong parameter
16 Incorrect 54 ms 6168 KB wrong parameter
17 Incorrect 61 ms 6268 KB wrong parameter
18 Incorrect 55 ms 6400 KB wrong parameter
19 Incorrect 41 ms 6008 KB wrong parameter
20 Incorrect 87 ms 6744 KB wrong parameter
21 Incorrect 96 ms 6792 KB wrong parameter
22 Incorrect 68 ms 6384 KB wrong parameter
23 Incorrect 82 ms 7064 KB wrong parameter