oj.uz

답안 #371226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371226 2021-02-26T07:38:01 Z Sorting 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 392 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);

    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[u] - d[par[u]]);
}

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(), 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 262148 KB Execution killed with signal 9
2 Runtime error 160 ms 262148 KB Execution killed with signal 9
3 Runtime error 171 ms 262148 KB Execution killed with signal 9
4 Runtime error 158 ms 262144 KB Execution killed with signal 9
5 Runtime error 183 ms 262148 KB Execution killed with signal 9
6 Runtime error 168 ms 262148 KB Execution killed with signal 9
7 Runtime error 199 ms 262148 KB Execution killed with signal 9
8 Runtime error 187 ms 262148 KB Execution killed with signal 9
9 Runtime error 164 ms 262144 KB Execution killed with signal 9
10 Runtime error 173 ms 262148 KB Execution killed with signal 9
11 Runtime error 181 ms 262144 KB Execution killed with signal 9
12 Incorrect 31 ms 5600 KB Output isn't correct
13 Runtime error 196 ms 262148 KB Execution killed with signal 9
14 Runtime error 170 ms 262148 KB Execution killed with signal 9
15 Runtime error 164 ms 262144 KB Execution killed with signal 9
16 Runtime error 187 ms 262148 KB Execution killed with signal 9
17 Runtime error 187 ms 262148 KB Execution killed with signal 9
18 Runtime error 195 ms 262148 KB Execution killed with signal 9
19 Runtime error 180 ms 262148 KB Execution killed with signal 9
20 Runtime error 221 ms 262148 KB Execution killed with signal 9
21 Runtime error 227 ms 262148 KB Execution killed with signal 9
22 Runtime error 193 ms 262148 KB Execution killed with signal 9
23 Runtime error 217 ms 262148 KB Execution killed with signal 9

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 262148 KB Execution killed with signal 9
2 Runtime error 160 ms 262148 KB Execution killed with signal 9
3 Runtime error 171 ms 262148 KB Execution killed with signal 9
4 Runtime error 158 ms 262144 KB Execution killed with signal 9
5 Runtime error 183 ms 262148 KB Execution killed with signal 9
6 Runtime error 168 ms 262148 KB Execution killed with signal 9
7 Runtime error 199 ms 262148 KB Execution killed with signal 9
8 Runtime error 187 ms 262148 KB Execution killed with signal 9
9 Runtime error 164 ms 262144 KB Execution killed with signal 9
10 Runtime error 173 ms 262148 KB Execution killed with signal 9
11 Runtime error 181 ms 262144 KB Execution killed with signal 9
12 Incorrect 31 ms 5600 KB Output isn't correct
13 Runtime error 196 ms 262148 KB Execution killed with signal 9
14 Runtime error 170 ms 262148 KB Execution killed with signal 9
15 Runtime error 164 ms 262144 KB Execution killed with signal 9
16 Runtime error 187 ms 262148 KB Execution killed with signal 9
17 Runtime error 187 ms 262148 KB Execution killed with signal 9
18 Runtime error 195 ms 262148 KB Execution killed with signal 9
19 Runtime error 180 ms 262148 KB Execution killed with signal 9
20 Runtime error 221 ms 262148 KB Execution killed with signal 9
21 Runtime error 227 ms 262148 KB Execution killed with signal 9
22 Runtime error 193 ms 262148 KB Execution killed with signal 9
23 Runtime error 217 ms 262148 KB Execution killed with signal 9

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 262148 KB Execution killed with signal 9
2 Runtime error 160 ms 262148 KB Execution killed with signal 9
3 Runtime error 171 ms 262148 KB Execution killed with signal 9
4 Runtime error 158 ms 262144 KB Execution killed with signal 9
5 Runtime error 183 ms 262148 KB Execution killed with signal 9
6 Runtime error 168 ms 262148 KB Execution killed with signal 9
7 Runtime error 199 ms 262148 KB Execution killed with signal 9
8 Runtime error 187 ms 262148 KB Execution killed with signal 9
9 Runtime error 164 ms 262144 KB Execution killed with signal 9
10 Runtime error 173 ms 262148 KB Execution killed with signal 9
11 Runtime error 181 ms 262144 KB Execution killed with signal 9
12 Incorrect 31 ms 5600 KB Output isn't correct
13 Runtime error 196 ms 262148 KB Execution killed with signal 9
14 Runtime error 170 ms 262148 KB Execution killed with signal 9
15 Runtime error 164 ms 262144 KB Execution killed with signal 9
16 Runtime error 187 ms 262148 KB Execution killed with signal 9
17 Runtime error 187 ms 262148 KB Execution killed with signal 9
18 Runtime error 195 ms 262148 KB Execution killed with signal 9
19 Runtime error 180 ms 262148 KB Execution killed with signal 9
20 Runtime error 221 ms 262148 KB Execution killed with signal 9
21 Runtime error 227 ms 262148 KB Execution killed with signal 9
22 Runtime error 193 ms 262148 KB Execution killed with signal 9
23 Runtime error 217 ms 262148 KB Execution killed with signal 9

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 262148 KB Execution killed with signal 9
2 Runtime error 160 ms 262148 KB Execution killed with signal 9
3 Runtime error 171 ms 262148 KB Execution killed with signal 9
4 Runtime error 158 ms 262144 KB Execution killed with signal 9
5 Runtime error 183 ms 262148 KB Execution killed with signal 9
6 Runtime error 168 ms 262148 KB Execution killed with signal 9
7 Runtime error 199 ms 262148 KB Execution killed with signal 9
8 Runtime error 187 ms 262148 KB Execution killed with signal 9
9 Runtime error 164 ms 262144 KB Execution killed with signal 9
10 Runtime error 173 ms 262148 KB Execution killed with signal 9
11 Runtime error 181 ms 262144 KB Execution killed with signal 9
12 Incorrect 31 ms 5600 KB Output isn't correct
13 Runtime error 196 ms 262148 KB Execution killed with signal 9
14 Runtime error 170 ms 262148 KB Execution killed with signal 9
15 Runtime error 164 ms 262144 KB Execution killed with signal 9
16 Runtime error 187 ms 262148 KB Execution killed with signal 9
17 Runtime error 187 ms 262148 KB Execution killed with signal 9
18 Runtime error 195 ms 262148 KB Execution killed with signal 9
19 Runtime error 180 ms 262148 KB Execution killed with signal 9
20 Runtime error 221 ms 262148 KB Execution killed with signal 9
21 Runtime error 227 ms 262148 KB Execution killed with signal 9
22 Runtime error 193 ms 262148 KB Execution killed with signal 9
23 Runtime error 217 ms 262148 KB Execution killed with signal 9