oj.uz

Submission #394821

# Submission time Handle Problem Language Result Execution time Memory
394821 2021-04-27T10:36:37 Z MarcoMeijer Saveit (IOI10_saveit) C++14
0 / 100
 276 ms 10812 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
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void writeSmallInt(int x) {
    RE(i,10) {
        bool b = false;
        if(x & (1<<i)) b = 1;
        encode_bit(b);
    }
}

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]);
    }
    RE(i,ne) random_shuffle(all(adj[i]), [](int x){return rng()%x;});

    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;
                usedEdges.insert({min(u,v),max(u,v)});
                q.push(v);
            }
        }
    }

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

    RE(i,nv) {
        writeSmallInt(adj[i].size());
        FOR(v,adj[i]) writeSmallInt(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 res = 0;
    RE(i,10) {
        bool b = decode_bit();
        if(b) res |= (1<<i);
    }
    return res;
}

void decode(int nv, int nh) {
    // reconstruct graph
    vector<vi> adj; adj.resize(nv);
    RE(u,nv) {
        int sz = readSmallInt();
        RE(j,sz) {
            int v = readSmallInt();
            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);
            }
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 10812 KB Execution killed with signal 11
2 Runtime error 4 ms 456 KB Execution killed with signal 11
3 Runtime error 10 ms 968 KB Execution killed with signal 11
4 Runtime error 4 ms 416 KB Execution killed with signal 11
5 Runtime error 12 ms 1160 KB Execution killed with signal 11
6 Runtime error 15 ms 1260 KB Execution killed with signal 11
7 Runtime error 34 ms 1884 KB Execution killed with signal 11
8 Runtime error 9 ms 860 KB Execution killed with signal 11
9 Runtime error 12 ms 968 KB Execution killed with signal 11
10 Runtime error 10 ms 932 KB Execution killed with signal 11
11 Runtime error 13 ms 1224 KB Execution killed with signal 11
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Runtime error 49 ms 2212 KB Execution killed with signal 11
14 Runtime error 11 ms 968 KB Execution killed with signal 11
15 Runtime error 14 ms 968 KB Execution killed with signal 11
16 Runtime error 32 ms 1932 KB Execution killed with signal 11
17 Runtime error 27 ms 1856 KB Execution killed with signal 11
18 Runtime error 34 ms 2508 KB Execution killed with signal 11
19 Runtime error 21 ms 1584 KB Execution killed with signal 11
20 Runtime error 53 ms 3032 KB Execution killed with signal 11
21 Runtime error 82 ms 3264 KB Execution killed with signal 11
22 Runtime error 37 ms 2196 KB Execution killed with signal 11
23 Runtime error 64 ms 3776 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 10812 KB Execution killed with signal 11
2 Runtime error 4 ms 456 KB Execution killed with signal 11
3 Runtime error 10 ms 968 KB Execution killed with signal 11
4 Runtime error 4 ms 416 KB Execution killed with signal 11
5 Runtime error 12 ms 1160 KB Execution killed with signal 11
6 Runtime error 15 ms 1260 KB Execution killed with signal 11
7 Runtime error 34 ms 1884 KB Execution killed with signal 11
8 Runtime error 9 ms 860 KB Execution killed with signal 11
9 Runtime error 12 ms 968 KB Execution killed with signal 11
10 Runtime error 10 ms 932 KB Execution killed with signal 11
11 Runtime error 13 ms 1224 KB Execution killed with signal 11
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Runtime error 49 ms 2212 KB Execution killed with signal 11
14 Runtime error 11 ms 968 KB Execution killed with signal 11
15 Runtime error 14 ms 968 KB Execution killed with signal 11
16 Runtime error 32 ms 1932 KB Execution killed with signal 11
17 Runtime error 27 ms 1856 KB Execution killed with signal 11
18 Runtime error 34 ms 2508 KB Execution killed with signal 11
19 Runtime error 21 ms 1584 KB Execution killed with signal 11
20 Runtime error 53 ms 3032 KB Execution killed with signal 11
21 Runtime error 82 ms 3264 KB Execution killed with signal 11
22 Runtime error 37 ms 2196 KB Execution killed with signal 11
23 Runtime error 64 ms 3776 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 10812 KB Execution killed with signal 11
2 Runtime error 4 ms 456 KB Execution killed with signal 11
3 Runtime error 10 ms 968 KB Execution killed with signal 11
4 Runtime error 4 ms 416 KB Execution killed with signal 11
5 Runtime error 12 ms 1160 KB Execution killed with signal 11
6 Runtime error 15 ms 1260 KB Execution killed with signal 11
7 Runtime error 34 ms 1884 KB Execution killed with signal 11
8 Runtime error 9 ms 860 KB Execution killed with signal 11
9 Runtime error 12 ms 968 KB Execution killed with signal 11
10 Runtime error 10 ms 932 KB Execution killed with signal 11
11 Runtime error 13 ms 1224 KB Execution killed with signal 11
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Runtime error 49 ms 2212 KB Execution killed with signal 11
14 Runtime error 11 ms 968 KB Execution killed with signal 11
15 Runtime error 14 ms 968 KB Execution killed with signal 11
16 Runtime error 32 ms 1932 KB Execution killed with signal 11
17 Runtime error 27 ms 1856 KB Execution killed with signal 11
18 Runtime error 34 ms 2508 KB Execution killed with signal 11
19 Runtime error 21 ms 1584 KB Execution killed with signal 11
20 Runtime error 53 ms 3032 KB Execution killed with signal 11
21 Runtime error 82 ms 3264 KB Execution killed with signal 11
22 Runtime error 37 ms 2196 KB Execution killed with signal 11
23 Runtime error 64 ms 3776 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 10812 KB Execution killed with signal 11
2 Runtime error 4 ms 456 KB Execution killed with signal 11
3 Runtime error 10 ms 968 KB Execution killed with signal 11
4 Runtime error 4 ms 416 KB Execution killed with signal 11
5 Runtime error 12 ms 1160 KB Execution killed with signal 11
6 Runtime error 15 ms 1260 KB Execution killed with signal 11
7 Runtime error 34 ms 1884 KB Execution killed with signal 11
8 Runtime error 9 ms 860 KB Execution killed with signal 11
9 Runtime error 12 ms 968 KB Execution killed with signal 11
10 Runtime error 10 ms 932 KB Execution killed with signal 11
11 Runtime error 13 ms 1224 KB Execution killed with signal 11
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Runtime error 49 ms 2212 KB Execution killed with signal 11
14 Runtime error 11 ms 968 KB Execution killed with signal 11
15 Runtime error 14 ms 968 KB Execution killed with signal 11
16 Runtime error 32 ms 1932 KB Execution killed with signal 11
17 Runtime error 27 ms 1856 KB Execution killed with signal 11
18 Runtime error 34 ms 2508 KB Execution killed with signal 11
19 Runtime error 21 ms 1584 KB Execution killed with signal 11
20 Runtime error 53 ms 3032 KB Execution killed with signal 11
21 Runtime error 82 ms 3264 KB Execution killed with signal 11
22 Runtime error 37 ms 2196 KB Execution killed with signal 11
23 Runtime error 64 ms 3776 KB Execution killed with signal 11