oj.uz

Submission #371238

# Submission time Handle Problem Language Result Execution time Memory
371238 2021-02-26T09:04:17 Z Sorting Saveit (IOI10_saveit) C++17
0 / 100
 393 ms 262148 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;
const int INF = 1e9;

static vector<int> adj[N];
static int n, h, m, par[N], d[N];
static bool vis[N];

void encode_num(int x){
    for(int i = 9; i >= 0; --i)
        encode_bit((x >> i) & 1);
}

void encode_diff(int diff){
    if(diff == -1){
        encode_bit(0);
        encode_bit(0);
    }
    else if(!diff){
        encode_bit(0);
        encode_bit(1);
    }
    else{
        encode_bit(1);
        encode_bit(0);
    }
}

void dfs(int u, int p = -1){
    vis[u] = true;
    par[u] = p;

    for(int to: adj[u])
        if(to != p)
            dfs(to, u);
}

void bfs(int u){
    fill(d, d + n, INF);

    queue<int> q;
    q.push(u);
    d[u] = 0;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(d[to] == INF){
                d[to] = d[u] + 1;
                q.push(to);
            }
    }

    for(int i = 1; i < n; ++i)
        encode_diff(d[i] - d[par[i]]);
}

void encode(int _nv, int _nh, int _ne, int *v1, int *v2){
    n = _nv, h =_nh, m = _ne;
    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 0; i < m; ++i){
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    fill(vis, vis + n, false);
    dfs(0);
    for(int i = 1; i < n; ++i)
        encode_num(par[i]);

    for(int i = 1; i < h; ++i)
        bfs(i);
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;

static int n, h, par[N], d[N];
static vector<int> adj[N];
static bool vis[N];

int decode_diff(){
    int bit1 = decode_bit();
    int bit2 = decode_bit();
    if(bit1) return 1;
    if(bit2) return 0;
    return -1;
}

int decode_num(){
    int num = 0;
    for(int i = 9; i >= 0; --i)
        if(decode_bit())
            num += (1 << i);
    return num;
}

void dfs(int u){
    hops(0, u, d[u]);
    for(int to: adj[u]){
        if(to == par[u]) continue;
        d[to] = d[u] + 1;
        dfs(to);
    }
}

void dfs2(int hub, int u, int ans){
    hops(hub, u, ans);
    vis[u] = true;
    for(int to: adj[u])
        if(!vis[to]){
            if(to == par[u]) dfs2(hub, to, ans - d[u]);
            else dfs2(hub, to, ans + d[u]);
        }
}

void decode(int _nv, int _nh) {
    n = _nv, h = _nh;
    if(n == 1){
        hops(0, 0, 0);
        return;
    }

    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 1; i < n; ++i){
        par[i] = decode_num();
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
    d[0] = 0;
    dfs(0);

    for(int i = 1; i < h; ++i){
        for(int j = 1; j < n; ++j)
            d[j] = decode_diff();
        fill(vis, vis + n, false);
        dfs2(i, i, 0);
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 393 ms 262148 KB Execution killed with signal 9
2 Runtime error 170 ms 262148 KB Execution killed with signal 9
3 Runtime error 195 ms 262148 KB Execution killed with signal 9
4 Runtime error 171 ms 262148 KB Execution killed with signal 9
5 Runtime error 176 ms 262148 KB Execution killed with signal 9
6 Runtime error 181 ms 262148 KB Execution killed with signal 9
7 Runtime error 201 ms 262144 KB Execution killed with signal 9
8 Runtime error 193 ms 262148 KB Execution killed with signal 9
9 Runtime error 175 ms 262148 KB Execution killed with signal 9
10 Runtime error 178 ms 262148 KB Execution killed with signal 9
11 Runtime error 206 ms 262148 KB Execution killed with signal 9
12 Incorrect 25 ms 5600 KB wrong parameter
13 Runtime error 202 ms 262148 KB Execution killed with signal 9
14 Runtime error 171 ms 262148 KB Execution killed with signal 9
15 Runtime error 179 ms 262148 KB Execution killed with signal 9
16 Runtime error 201 ms 262148 KB Execution killed with signal 9
17 Runtime error 205 ms 262148 KB Execution killed with signal 9
18 Runtime error 197 ms 262148 KB Execution killed with signal 9
19 Runtime error 193 ms 262148 KB Execution killed with signal 9
20 Runtime error 234 ms 262148 KB Execution killed with signal 9
21 Runtime error 240 ms 262148 KB Execution killed with signal 9
22 Runtime error 207 ms 262148 KB Execution killed with signal 9
23 Runtime error 225 ms 262148 KB Execution killed with signal 9

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 393 ms 262148 KB Execution killed with signal 9
2 Runtime error 170 ms 262148 KB Execution killed with signal 9
3 Runtime error 195 ms 262148 KB Execution killed with signal 9
4 Runtime error 171 ms 262148 KB Execution killed with signal 9
5 Runtime error 176 ms 262148 KB Execution killed with signal 9
6 Runtime error 181 ms 262148 KB Execution killed with signal 9
7 Runtime error 201 ms 262144 KB Execution killed with signal 9
8 Runtime error 193 ms 262148 KB Execution killed with signal 9
9 Runtime error 175 ms 262148 KB Execution killed with signal 9
10 Runtime error 178 ms 262148 KB Execution killed with signal 9
11 Runtime error 206 ms 262148 KB Execution killed with signal 9
12 Incorrect 25 ms 5600 KB wrong parameter
13 Runtime error 202 ms 262148 KB Execution killed with signal 9
14 Runtime error 171 ms 262148 KB Execution killed with signal 9
15 Runtime error 179 ms 262148 KB Execution killed with signal 9
16 Runtime error 201 ms 262148 KB Execution killed with signal 9
17 Runtime error 205 ms 262148 KB Execution killed with signal 9
18 Runtime error 197 ms 262148 KB Execution killed with signal 9
19 Runtime error 193 ms 262148 KB Execution killed with signal 9
20 Runtime error 234 ms 262148 KB Execution killed with signal 9
21 Runtime error 240 ms 262148 KB Execution killed with signal 9
22 Runtime error 207 ms 262148 KB Execution killed with signal 9
23 Runtime error 225 ms 262148 KB Execution killed with signal 9

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 393 ms 262148 KB Execution killed with signal 9
2 Runtime error 170 ms 262148 KB Execution killed with signal 9
3 Runtime error 195 ms 262148 KB Execution killed with signal 9
4 Runtime error 171 ms 262148 KB Execution killed with signal 9
5 Runtime error 176 ms 262148 KB Execution killed with signal 9
6 Runtime error 181 ms 262148 KB Execution killed with signal 9
7 Runtime error 201 ms 262144 KB Execution killed with signal 9
8 Runtime error 193 ms 262148 KB Execution killed with signal 9
9 Runtime error 175 ms 262148 KB Execution killed with signal 9
10 Runtime error 178 ms 262148 KB Execution killed with signal 9
11 Runtime error 206 ms 262148 KB Execution killed with signal 9
12 Incorrect 25 ms 5600 KB wrong parameter
13 Runtime error 202 ms 262148 KB Execution killed with signal 9
14 Runtime error 171 ms 262148 KB Execution killed with signal 9
15 Runtime error 179 ms 262148 KB Execution killed with signal 9
16 Runtime error 201 ms 262148 KB Execution killed with signal 9
17 Runtime error 205 ms 262148 KB Execution killed with signal 9
18 Runtime error 197 ms 262148 KB Execution killed with signal 9
19 Runtime error 193 ms 262148 KB Execution killed with signal 9
20 Runtime error 234 ms 262148 KB Execution killed with signal 9
21 Runtime error 240 ms 262148 KB Execution killed with signal 9
22 Runtime error 207 ms 262148 KB Execution killed with signal 9
23 Runtime error 225 ms 262148 KB Execution killed with signal 9

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 393 ms 262148 KB Execution killed with signal 9
2 Runtime error 170 ms 262148 KB Execution killed with signal 9
3 Runtime error 195 ms 262148 KB Execution killed with signal 9
4 Runtime error 171 ms 262148 KB Execution killed with signal 9
5 Runtime error 176 ms 262148 KB Execution killed with signal 9
6 Runtime error 181 ms 262148 KB Execution killed with signal 9
7 Runtime error 201 ms 262144 KB Execution killed with signal 9
8 Runtime error 193 ms 262148 KB Execution killed with signal 9
9 Runtime error 175 ms 262148 KB Execution killed with signal 9
10 Runtime error 178 ms 262148 KB Execution killed with signal 9
11 Runtime error 206 ms 262148 KB Execution killed with signal 9
12 Incorrect 25 ms 5600 KB wrong parameter
13 Runtime error 202 ms 262148 KB Execution killed with signal 9
14 Runtime error 171 ms 262148 KB Execution killed with signal 9
15 Runtime error 179 ms 262148 KB Execution killed with signal 9
16 Runtime error 201 ms 262148 KB Execution killed with signal 9
17 Runtime error 205 ms 262148 KB Execution killed with signal 9
18 Runtime error 197 ms 262148 KB Execution killed with signal 9
19 Runtime error 193 ms 262148 KB Execution killed with signal 9
20 Runtime error 234 ms 262148 KB Execution killed with signal 9
21 Runtime error 240 ms 262148 KB Execution killed with signal 9
22 Runtime error 207 ms 262148 KB Execution killed with signal 9
23 Runtime error 225 ms 262148 KB Execution killed with signal 9