oj.uz

답안 #566118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566118 2022-05-21T20:19:03 Z RealSnake 저장 (Saveit) (IOI10_saveit) C++14
0 / 100
 213 ms 11940 KB 
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "encoder.h"

void encode(int n, int h, int p, int a[], int b[]) {
    vector<int> v[n];
    for(int i = 0; i < p; i++) {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    set<int> s;
    s.insert(0);
    bool par[n] = {};
    par[0] = 1;
    vector<int> v2[n];
    while(s.size()) {
        int x = *s.begin();
        s.erase(s.begin());
        for(int i : v[x]) {
            if(!par[i]) {
                v2[x].push_back(i);
                par[i] = x + 1;
                s.insert(i);
            }
        }
        sort(v[x].begin(), v[x].end());
    }
    for(int i = 0; i < n; i++) {
        int x = par[i] - 1;
        for(int j = 0; j < 10; j++)
            encode_bit((x & (1 << j) > 0));
    }
    int ans[n][h];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < h; j++)
            ans[i][j] = 1e9;
    }
    set<pair<int, pair<int, int>>> ss;
    for(int i = 0; i < h; i++) {
        ss.insert({0, {i, i}});
        ans[i][i] = 0;
    }
    while(ss.size()) {
        pair<int, pair<int, int>> p = *ss.begin();
        ss.erase(ss.begin());
        int x = p.second.first, hub = p.second.second;
        int cost = p.first;
        if(cost > ans[x][hub])
            continue;
        for(int i : v[x]) {
            if(cost + 1 < ans[i][hub]) {
                ans[i][hub] = cost + 1;
                ss.insert({cost + 1, {i, hub}});
            }
        }
    }
    for(int i = 0; i < h; i++) {
        int x = ans[0][i];
        for(int j = 0; j < 10; j++)
            encode_bit((x & (1 << j) > 0));
        s.insert(0);
        while(s.size()) {
            x = *s.begin();
            s.erase(s.begin());
            for(int j : v2[x]) {
                int dif = ans[j][i] - ans[x][i];
                if(dif == 0)
                    encode_bit(0);
                else {
                    encode_bit(1);
                    if(dif == 1)
                        encode_bit(1);
                    else
                        encode_bit(0);
                }
            }
        }
    }
}
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "decoder.h"

void decode(int n, int h) {
    vector<int> v[n];
    for(int i = 0; i < n; i++) {
        int x = 0;
        for(int j = 0; j < 10; j++) {
            if(decode_bit())
                x += (1 << j);
        }
        if(i != x)
            v[x].push_back(i);
    }
    for(int i = 0; i < h; i++) {
        int b[n];
        b[0] = 0;
        for(int j = 0; j < 10; j++) {
            if(decode_bit())
                b[0] += (1 << j);
        }
        set<int> s;
        s.insert(0);
        while(s.size()) {
            int x = *s.begin();
            s.erase(s.begin());
            hops(i, x, b[x]);
            for(int j : v[x]) {
                int dif = decode_bit();
                if(dif) {
                    if(!decode_bit())
                        dif = -1;
                }
                b[j] = b[x] + dif;
                s.insert(j);
            }
        }
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:32:38: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   32 |             encode_bit((x & (1 << j) > 0));
      |                             ~~~~~~~~~^~~
encoder.cpp:61:38: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   61 |             encode_bit((x & (1 << j) > 0));
      |                             ~~~~~~~~~^~~

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 11940 KB wrong parameter
2 Incorrect 1 ms 4488 KB wrong parameter
3 Incorrect 16 ms 6256 KB too many decode_bit() calls
4 Incorrect 2 ms 4608 KB wrong parameter
5 Incorrect 19 ms 6912 KB wrong parameter
6 Incorrect 19 ms 7020 KB too many decode_bit() calls
7 Incorrect 39 ms 7664 KB wrong parameter
8 Incorrect 14 ms 5252 KB too many decode_bit() calls
9 Incorrect 13 ms 5256 KB too many decode_bit() calls
10 Incorrect 17 ms 5316 KB wrong parameter
11 Incorrect 16 ms 5436 KB too many decode_bit() calls
12 Incorrect 13 ms 5116 KB too many decode_bit() calls
13 Incorrect 41 ms 7084 KB wrong parameter
14 Incorrect 15 ms 5240 KB too many decode_bit() calls
15 Incorrect 16 ms 5236 KB wrong parameter
16 Incorrect 35 ms 5668 KB too many decode_bit() calls
17 Incorrect 35 ms 5880 KB wrong parameter
18 Incorrect 41 ms 6248 KB wrong parameter
19 Incorrect 27 ms 5996 KB wrong parameter
20 Incorrect 57 ms 7196 KB too many decode_bit() calls
21 Incorrect 66 ms 6976 KB wrong parameter
22 Incorrect 39 ms 7472 KB wrong parameter
23 Incorrect 58 ms 8100 KB too many decode_bit() calls

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 11940 KB wrong parameter
2 Incorrect 1 ms 4488 KB wrong parameter
3 Incorrect 16 ms 6256 KB too many decode_bit() calls
4 Incorrect 2 ms 4608 KB wrong parameter
5 Incorrect 19 ms 6912 KB wrong parameter
6 Incorrect 19 ms 7020 KB too many decode_bit() calls
7 Incorrect 39 ms 7664 KB wrong parameter
8 Incorrect 14 ms 5252 KB too many decode_bit() calls
9 Incorrect 13 ms 5256 KB too many decode_bit() calls
10 Incorrect 17 ms 5316 KB wrong parameter
11 Incorrect 16 ms 5436 KB too many decode_bit() calls
12 Incorrect 13 ms 5116 KB too many decode_bit() calls
13 Incorrect 41 ms 7084 KB wrong parameter
14 Incorrect 15 ms 5240 KB too many decode_bit() calls
15 Incorrect 16 ms 5236 KB wrong parameter
16 Incorrect 35 ms 5668 KB too many decode_bit() calls
17 Incorrect 35 ms 5880 KB wrong parameter
18 Incorrect 41 ms 6248 KB wrong parameter
19 Incorrect 27 ms 5996 KB wrong parameter
20 Incorrect 57 ms 7196 KB too many decode_bit() calls
21 Incorrect 66 ms 6976 KB wrong parameter
22 Incorrect 39 ms 7472 KB wrong parameter
23 Incorrect 58 ms 8100 KB too many decode_bit() calls

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 11940 KB wrong parameter
2 Incorrect 1 ms 4488 KB wrong parameter
3 Incorrect 16 ms 6256 KB too many decode_bit() calls
4 Incorrect 2 ms 4608 KB wrong parameter
5 Incorrect 19 ms 6912 KB wrong parameter
6 Incorrect 19 ms 7020 KB too many decode_bit() calls
7 Incorrect 39 ms 7664 KB wrong parameter
8 Incorrect 14 ms 5252 KB too many decode_bit() calls
9 Incorrect 13 ms 5256 KB too many decode_bit() calls
10 Incorrect 17 ms 5316 KB wrong parameter
11 Incorrect 16 ms 5436 KB too many decode_bit() calls
12 Incorrect 13 ms 5116 KB too many decode_bit() calls
13 Incorrect 41 ms 7084 KB wrong parameter
14 Incorrect 15 ms 5240 KB too many decode_bit() calls
15 Incorrect 16 ms 5236 KB wrong parameter
16 Incorrect 35 ms 5668 KB too many decode_bit() calls
17 Incorrect 35 ms 5880 KB wrong parameter
18 Incorrect 41 ms 6248 KB wrong parameter
19 Incorrect 27 ms 5996 KB wrong parameter
20 Incorrect 57 ms 7196 KB too many decode_bit() calls
21 Incorrect 66 ms 6976 KB wrong parameter
22 Incorrect 39 ms 7472 KB wrong parameter
23 Incorrect 58 ms 8100 KB too many decode_bit() calls

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 11940 KB wrong parameter
2 Incorrect 1 ms 4488 KB wrong parameter
3 Incorrect 16 ms 6256 KB too many decode_bit() calls
4 Incorrect 2 ms 4608 KB wrong parameter
5 Incorrect 19 ms 6912 KB wrong parameter
6 Incorrect 19 ms 7020 KB too many decode_bit() calls
7 Incorrect 39 ms 7664 KB wrong parameter
8 Incorrect 14 ms 5252 KB too many decode_bit() calls
9 Incorrect 13 ms 5256 KB too many decode_bit() calls
10 Incorrect 17 ms 5316 KB wrong parameter
11 Incorrect 16 ms 5436 KB too many decode_bit() calls
12 Incorrect 13 ms 5116 KB too many decode_bit() calls
13 Incorrect 41 ms 7084 KB wrong parameter
14 Incorrect 15 ms 5240 KB too many decode_bit() calls
15 Incorrect 16 ms 5236 KB wrong parameter
16 Incorrect 35 ms 5668 KB too many decode_bit() calls
17 Incorrect 35 ms 5880 KB wrong parameter
18 Incorrect 41 ms 6248 KB wrong parameter
19 Incorrect 27 ms 5996 KB wrong parameter
20 Incorrect 57 ms 7196 KB too many decode_bit() calls
21 Incorrect 66 ms 6976 KB wrong parameter
22 Incorrect 39 ms 7472 KB wrong parameter
23 Incorrect 58 ms 8100 KB too many decode_bit() calls