oj.uz

Submission #394933

# Submission time Handle Problem Language Result Execution time Memory
394933 2021-04-27T13:58:39 Z MarcoMeijer Saveit (IOI10_saveit) C++14
50 / 100
 644 ms 35308 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);
    set<ii> difEdges;
    RE(i,ne) {
        adj[v1[i]].pb(v2[i]);
        adj[v2[i]].pb(v1[i]);
        difEdges.insert({v1[i],v2[i]});
        difEdges.insert({v2[i],v1[i]});
    }

    set<ii> usedEdges;
    RE(h,nh) {
        // bfs
        vi dist; dist.assign(nv, -1);
        queue<int> q;
        q.push(h); dist[h] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            FOR(v,adj[u]) {
                if(dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
        
        vi prev = {h};
        RE1(i,nv) {
            vi cur;
            RE(u,nv) if(dist[u] == i) cur.pb(u);
            FOR(u,cur) {
                bool found = false;
                FOR(v,prev) if(usedEdges.count({min(u,v),max(u,v)})) {
                    found = true;
                    break;
                }
                if(!found) FOR(v,prev) if(difEdges.count({u,v})) {
                    usedEdges.insert({min(u,v),max(u,v)});
                    break;
                }
            }
            if(cur.empty()) break;
            prev = cur;
        }
    }

    RE(i,nv) adj[i].clear();
    FOR(p,usedEdges) adj[p.se].pb(p.fi);

    RE(i,nv) {
        writeSmallInt(adj[i].size(), 10);
        int minBits = maxBits(i-1);
        if(minBits * adj[i].size() <= i-1) {
            FOR(v,adj[i]) writeSmallInt(v, minBits);
        } else {
            bitset<1000> bs; bs.reset();
            FOR(v,adj[i]) bs[v] = 1;
            RE(v,i) encode_bit(bs[v]);
        }
    }
}

#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 maxBits(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) {
    // reconstruct graph
    vector<vi> adj; adj.resize(nv);
    RE(u,nv) {
        int sz = readSmallInt(10);
        int minBits = maxBits(u-1);
        if(minBits * sz <= u-1) {
            RE(j,sz) {
                int v = readSmallInt(minBits);
                adj[u].pb(v);
                adj[v].pb(u);
            }
        } else {
            RE(v,u) if(decode_bit()) adj[u].pb(v), adj[v].pb(u);
        }
    }

    RE(h,nh) {
        // bfs
        vi dist; dist.assign(nv, -1);
        queue<int> q;
        q.push(h); dist[h] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            hops(h,u,dist[u]);
            FOR(v,adj[u]) {
                if(dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:95:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if(minBits * adj[i].size() <= i-1) {
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 35308 KB Output is partially correct - 166272 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 59 call(s) of encode_bit()
3 Correct 149 ms 5692 KB Output is correct - 42093 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 59 call(s) of encode_bit()
5 Correct 151 ms 6776 KB Output is partially correct - 82354 call(s) of encode_bit()
6 Correct 189 ms 6936 KB Output is partially correct - 84902 call(s) of encode_bit()
7 Correct 225 ms 9936 KB Output is partially correct - 151461 call(s) of encode_bit()
8 Correct 51 ms 5128 KB Output is correct - 25924 call(s) of encode_bit()
9 Correct 55 ms 5324 KB Output is correct - 25037 call(s) of encode_bit()
10 Correct 53 ms 5256 KB Output is correct - 24649 call(s) of encode_bit()
11 Correct 69 ms 6380 KB Output is correct - 38872 call(s) of encode_bit()
12 Correct 111 ms 4956 KB Output is correct - 19646 call(s) of encode_bit()
13 Correct 196 ms 10200 KB Output is partially correct - 87721 call(s) of encode_bit()
14 Correct 94 ms 5452 KB Output is correct - 29129 call(s) of encode_bit()
15 Correct 93 ms 5872 KB Output is correct - 30629 call(s) of encode_bit()
16 Correct 153 ms 9116 KB Output is correct - 43646 call(s) of encode_bit()
17 Correct 125 ms 8492 KB Output is correct - 47377 call(s) of encode_bit()
18 Correct 182 ms 9928 KB Output is correct - 59711 call(s) of encode_bit()
19 Correct 139 ms 7816 KB Output is correct - 67337 call(s) of encode_bit()
20 Correct 189 ms 11348 KB Output is partially correct - 71841 call(s) of encode_bit()
21 Correct 225 ms 12556 KB Output is partially correct - 72459 call(s) of encode_bit()
22 Correct 225 ms 10236 KB Output is partially correct - 123592 call(s) of encode_bit()
23 Correct 255 ms 13676 KB Output is partially correct - 103454 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 35308 KB Output is partially correct - 166272 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 59 call(s) of encode_bit()
3 Correct 149 ms 5692 KB Output is correct - 42093 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 59 call(s) of encode_bit()
5 Correct 151 ms 6776 KB Output is partially correct - 82354 call(s) of encode_bit()
6 Correct 189 ms 6936 KB Output is partially correct - 84902 call(s) of encode_bit()
7 Correct 225 ms 9936 KB Output is partially correct - 151461 call(s) of encode_bit()
8 Correct 51 ms 5128 KB Output is correct - 25924 call(s) of encode_bit()
9 Correct 55 ms 5324 KB Output is correct - 25037 call(s) of encode_bit()
10 Correct 53 ms 5256 KB Output is correct - 24649 call(s) of encode_bit()
11 Correct 69 ms 6380 KB Output is correct - 38872 call(s) of encode_bit()
12 Correct 111 ms 4956 KB Output is correct - 19646 call(s) of encode_bit()
13 Correct 196 ms 10200 KB Output is partially correct - 87721 call(s) of encode_bit()
14 Correct 94 ms 5452 KB Output is correct - 29129 call(s) of encode_bit()
15 Correct 93 ms 5872 KB Output is correct - 30629 call(s) of encode_bit()
16 Correct 153 ms 9116 KB Output is correct - 43646 call(s) of encode_bit()
17 Correct 125 ms 8492 KB Output is correct - 47377 call(s) of encode_bit()
18 Correct 182 ms 9928 KB Output is correct - 59711 call(s) of encode_bit()
19 Correct 139 ms 7816 KB Output is correct - 67337 call(s) of encode_bit()
20 Correct 189 ms 11348 KB Output is partially correct - 71841 call(s) of encode_bit()
21 Correct 225 ms 12556 KB Output is partially correct - 72459 call(s) of encode_bit()
22 Correct 225 ms 10236 KB Output is partially correct - 123592 call(s) of encode_bit()
23 Correct 255 ms 13676 KB Output is partially correct - 103454 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 35308 KB Output is partially correct - 166272 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 59 call(s) of encode_bit()
3 Correct 149 ms 5692 KB Output is correct - 42093 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 59 call(s) of encode_bit()
5 Correct 151 ms 6776 KB Output is partially correct - 82354 call(s) of encode_bit()
6 Correct 189 ms 6936 KB Output is partially correct - 84902 call(s) of encode_bit()
7 Correct 225 ms 9936 KB Output is partially correct - 151461 call(s) of encode_bit()
8 Correct 51 ms 5128 KB Output is correct - 25924 call(s) of encode_bit()
9 Correct 55 ms 5324 KB Output is correct - 25037 call(s) of encode_bit()
10 Correct 53 ms 5256 KB Output is correct - 24649 call(s) of encode_bit()
11 Correct 69 ms 6380 KB Output is correct - 38872 call(s) of encode_bit()
12 Correct 111 ms 4956 KB Output is correct - 19646 call(s) of encode_bit()
13 Correct 196 ms 10200 KB Output is partially correct - 87721 call(s) of encode_bit()
14 Correct 94 ms 5452 KB Output is correct - 29129 call(s) of encode_bit()
15 Correct 93 ms 5872 KB Output is correct - 30629 call(s) of encode_bit()
16 Correct 153 ms 9116 KB Output is correct - 43646 call(s) of encode_bit()
17 Correct 125 ms 8492 KB Output is correct - 47377 call(s) of encode_bit()
18 Correct 182 ms 9928 KB Output is correct - 59711 call(s) of encode_bit()
19 Correct 139 ms 7816 KB Output is correct - 67337 call(s) of encode_bit()
20 Correct 189 ms 11348 KB Output is partially correct - 71841 call(s) of encode_bit()
21 Correct 225 ms 12556 KB Output is partially correct - 72459 call(s) of encode_bit()
22 Correct 225 ms 10236 KB Output is partially correct - 123592 call(s) of encode_bit()
23 Correct 255 ms 13676 KB Output is partially correct - 103454 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 35308 KB Output is partially correct - 166272 call(s) of encode_bit()
2 Correct 3 ms 4584 KB Output is correct - 59 call(s) of encode_bit()
3 Correct 149 ms 5692 KB Output is correct - 42093 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 59 call(s) of encode_bit()
5 Correct 151 ms 6776 KB Output is partially correct - 82354 call(s) of encode_bit()
6 Correct 189 ms 6936 KB Output is partially correct - 84902 call(s) of encode_bit()
7 Correct 225 ms 9936 KB Output is partially correct - 151461 call(s) of encode_bit()
8 Correct 51 ms 5128 KB Output is correct - 25924 call(s) of encode_bit()
9 Correct 55 ms 5324 KB Output is correct - 25037 call(s) of encode_bit()
10 Correct 53 ms 5256 KB Output is correct - 24649 call(s) of encode_bit()
11 Correct 69 ms 6380 KB Output is correct - 38872 call(s) of encode_bit()
12 Correct 111 ms 4956 KB Output is correct - 19646 call(s) of encode_bit()
13 Correct 196 ms 10200 KB Output is partially correct - 87721 call(s) of encode_bit()
14 Correct 94 ms 5452 KB Output is correct - 29129 call(s) of encode_bit()
15 Correct 93 ms 5872 KB Output is correct - 30629 call(s) of encode_bit()
16 Correct 153 ms 9116 KB Output is correct - 43646 call(s) of encode_bit()
17 Correct 125 ms 8492 KB Output is correct - 47377 call(s) of encode_bit()
18 Correct 182 ms 9928 KB Output is correct - 59711 call(s) of encode_bit()
19 Correct 139 ms 7816 KB Output is correct - 67337 call(s) of encode_bit()
20 Correct 189 ms 11348 KB Output is partially correct - 71841 call(s) of encode_bit()
21 Correct 225 ms 12556 KB Output is partially correct - 72459 call(s) of encode_bit()
22 Correct 225 ms 10236 KB Output is partially correct - 123592 call(s) of encode_bit()
23 Correct 255 ms 13676 KB Output is partially correct - 103454 call(s) of encode_bit()