oj.uz

Submission #395014

# Submission time Handle Problem Language Result Execution time Memory
395014 2021-04-27T15:36:09 Z MarcoMeijer Saveit (IOI10_saveit) C++14
50 / 100
 236 ms 10164 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);
    }
}
int maxBits(int x) {
    int mx = 0;
    RE(i,10) if(x&(1<<i)) mx = max(mx, i+1);
    return mx;
}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    vector<vi> adj; adj.resize(nv);
    RE(i,ne) {
        adj[v1[i]].pb(v2[i]);
        adj[v2[i]].pb(v1[i]);
    }

    vector<vi> dist; dist.resize(nh);
    RE(h,nh) {
        // bfs
        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);
            }
        }
    }

    RE(i,nh) {
        RE(j,nv) {
            if(j <= i) continue;
            int lb=0, ub=nv-1;
            RE(x,i) {
                lb = max(lb, dist[x][j] - dist[x][i]);
                ub = min(ub, dist[x][j] + dist[x][i]);
            }
            int bits = maxBits(ub-lb);
            writeSmallInt(dist[i][j] - lb, bits);
        }
    }
}

#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;
}
int maxBits2(int x) {
    int mx = 0;
    RE(i,10) if(x&(1<<i)) mx = max(mx, i+1);
    return mx;
}

void decode(int nv, int nh) {
    vector<vi> dist; dist.assign(nh, vi(nv,0));
    RE(i,nh) {
        RE(j,nv) {
            if(j <= i) {
                dist[i][j] = dist[j][i];
                hops(i,j,dist[i][j]);
                continue;
            }
            int lb=0, ub=nv-1;
            RE(x,i) {
                lb = max(lb, dist[x][j] - dist[x][i]);
                ub = min(ub, dist[x][j] + dist[x][i]);
            }
            int bits = maxBits2(ub-lb);
            dist[i][j] = lb+readSmallInt(bits);
            hops(i,j,dist[i][j]);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10164 KB Output is correct - 48854 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 22 call(s) of encode_bit()
3 Correct 53 ms 5560 KB Output is partially correct - 87474 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 24 call(s) of encode_bit()
5 Correct 40 ms 5656 KB Output is partially correct - 73015 call(s) of encode_bit()
6 Correct 39 ms 5848 KB Output is partially correct - 83284 call(s) of encode_bit()
7 Correct 53 ms 6152 KB Output is partially correct - 82393 call(s) of encode_bit()
8 Correct 34 ms 5700 KB Output is partially correct - 80635 call(s) of encode_bit()
9 Correct 49 ms 6104 KB Output is partially correct - 134272 call(s) of encode_bit()
10 Correct 57 ms 5920 KB Output is partially correct - 121826 call(s) of encode_bit()
11 Correct 53 ms 6208 KB Output is partially correct - 133016 call(s) of encode_bit()
12 Correct 34 ms 5684 KB Output is partially correct - 83666 call(s) of encode_bit()
13 Correct 67 ms 6140 KB Output is partially correct - 73085 call(s) of encode_bit()
14 Correct 40 ms 5780 KB Output is partially correct - 99139 call(s) of encode_bit()
15 Correct 33 ms 5520 KB Output is partially correct - 71315 call(s) of encode_bit()
16 Correct 84 ms 6196 KB Output is partially correct - 80002 call(s) of encode_bit()
17 Correct 53 ms 6176 KB Output is partially correct - 83397 call(s) of encode_bit()
18 Correct 77 ms 6412 KB Output is partially correct - 82973 call(s) of encode_bit()
19 Correct 47 ms 6028 KB Output is partially correct - 89652 call(s) of encode_bit()
20 Correct 89 ms 6544 KB Output is correct - 69724 call(s) of encode_bit()
21 Correct 107 ms 6668 KB Output is partially correct - 75913 call(s) of encode_bit()
22 Correct 69 ms 6172 KB Output is partially correct - 82321 call(s) of encode_bit()
23 Correct 128 ms 6944 KB Output is partially correct - 77900 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10164 KB Output is correct - 48854 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 22 call(s) of encode_bit()
3 Correct 53 ms 5560 KB Output is partially correct - 87474 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 24 call(s) of encode_bit()
5 Correct 40 ms 5656 KB Output is partially correct - 73015 call(s) of encode_bit()
6 Correct 39 ms 5848 KB Output is partially correct - 83284 call(s) of encode_bit()
7 Correct 53 ms 6152 KB Output is partially correct - 82393 call(s) of encode_bit()
8 Correct 34 ms 5700 KB Output is partially correct - 80635 call(s) of encode_bit()
9 Correct 49 ms 6104 KB Output is partially correct - 134272 call(s) of encode_bit()
10 Correct 57 ms 5920 KB Output is partially correct - 121826 call(s) of encode_bit()
11 Correct 53 ms 6208 KB Output is partially correct - 133016 call(s) of encode_bit()
12 Correct 34 ms 5684 KB Output is partially correct - 83666 call(s) of encode_bit()
13 Correct 67 ms 6140 KB Output is partially correct - 73085 call(s) of encode_bit()
14 Correct 40 ms 5780 KB Output is partially correct - 99139 call(s) of encode_bit()
15 Correct 33 ms 5520 KB Output is partially correct - 71315 call(s) of encode_bit()
16 Correct 84 ms 6196 KB Output is partially correct - 80002 call(s) of encode_bit()
17 Correct 53 ms 6176 KB Output is partially correct - 83397 call(s) of encode_bit()
18 Correct 77 ms 6412 KB Output is partially correct - 82973 call(s) of encode_bit()
19 Correct 47 ms 6028 KB Output is partially correct - 89652 call(s) of encode_bit()
20 Correct 89 ms 6544 KB Output is correct - 69724 call(s) of encode_bit()
21 Correct 107 ms 6668 KB Output is partially correct - 75913 call(s) of encode_bit()
22 Correct 69 ms 6172 KB Output is partially correct - 82321 call(s) of encode_bit()
23 Correct 128 ms 6944 KB Output is partially correct - 77900 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10164 KB Output is correct - 48854 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 22 call(s) of encode_bit()
3 Correct 53 ms 5560 KB Output is partially correct - 87474 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 24 call(s) of encode_bit()
5 Correct 40 ms 5656 KB Output is partially correct - 73015 call(s) of encode_bit()
6 Correct 39 ms 5848 KB Output is partially correct - 83284 call(s) of encode_bit()
7 Correct 53 ms 6152 KB Output is partially correct - 82393 call(s) of encode_bit()
8 Correct 34 ms 5700 KB Output is partially correct - 80635 call(s) of encode_bit()
9 Correct 49 ms 6104 KB Output is partially correct - 134272 call(s) of encode_bit()
10 Correct 57 ms 5920 KB Output is partially correct - 121826 call(s) of encode_bit()
11 Correct 53 ms 6208 KB Output is partially correct - 133016 call(s) of encode_bit()
12 Correct 34 ms 5684 KB Output is partially correct - 83666 call(s) of encode_bit()
13 Correct 67 ms 6140 KB Output is partially correct - 73085 call(s) of encode_bit()
14 Correct 40 ms 5780 KB Output is partially correct - 99139 call(s) of encode_bit()
15 Correct 33 ms 5520 KB Output is partially correct - 71315 call(s) of encode_bit()
16 Correct 84 ms 6196 KB Output is partially correct - 80002 call(s) of encode_bit()
17 Correct 53 ms 6176 KB Output is partially correct - 83397 call(s) of encode_bit()
18 Correct 77 ms 6412 KB Output is partially correct - 82973 call(s) of encode_bit()
19 Correct 47 ms 6028 KB Output is partially correct - 89652 call(s) of encode_bit()
20 Correct 89 ms 6544 KB Output is correct - 69724 call(s) of encode_bit()
21 Correct 107 ms 6668 KB Output is partially correct - 75913 call(s) of encode_bit()
22 Correct 69 ms 6172 KB Output is partially correct - 82321 call(s) of encode_bit()
23 Correct 128 ms 6944 KB Output is partially correct - 77900 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10164 KB Output is correct - 48854 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 22 call(s) of encode_bit()
3 Correct 53 ms 5560 KB Output is partially correct - 87474 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 24 call(s) of encode_bit()
5 Correct 40 ms 5656 KB Output is partially correct - 73015 call(s) of encode_bit()
6 Correct 39 ms 5848 KB Output is partially correct - 83284 call(s) of encode_bit()
7 Correct 53 ms 6152 KB Output is partially correct - 82393 call(s) of encode_bit()
8 Correct 34 ms 5700 KB Output is partially correct - 80635 call(s) of encode_bit()
9 Correct 49 ms 6104 KB Output is partially correct - 134272 call(s) of encode_bit()
10 Correct 57 ms 5920 KB Output is partially correct - 121826 call(s) of encode_bit()
11 Correct 53 ms 6208 KB Output is partially correct - 133016 call(s) of encode_bit()
12 Correct 34 ms 5684 KB Output is partially correct - 83666 call(s) of encode_bit()
13 Correct 67 ms 6140 KB Output is partially correct - 73085 call(s) of encode_bit()
14 Correct 40 ms 5780 KB Output is partially correct - 99139 call(s) of encode_bit()
15 Correct 33 ms 5520 KB Output is partially correct - 71315 call(s) of encode_bit()
16 Correct 84 ms 6196 KB Output is partially correct - 80002 call(s) of encode_bit()
17 Correct 53 ms 6176 KB Output is partially correct - 83397 call(s) of encode_bit()
18 Correct 77 ms 6412 KB Output is partially correct - 82973 call(s) of encode_bit()
19 Correct 47 ms 6028 KB Output is partially correct - 89652 call(s) of encode_bit()
20 Correct 89 ms 6544 KB Output is correct - 69724 call(s) of encode_bit()
21 Correct 107 ms 6668 KB Output is partially correct - 75913 call(s) of encode_bit()
22 Correct 69 ms 6172 KB Output is partially correct - 82321 call(s) of encode_bit()
23 Correct 128 ms 6944 KB Output is partially correct - 77900 call(s) of encode_bit()