oj.uz

Submission #566120

# Submission time Handle Problem Language Result Execution time Memory
566120 2022-05-21T20:20:27 Z RealSnake Saveit (IOI10_saveit) C++14
0 / 100
 209 ms 11932 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);
            }
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 11932 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 100 call(s) of encode_bit()
3 Incorrect 16 ms 6280 KB wrong parameter
4 Correct 3 ms 4704 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 6892 KB wrong parameter
6 Incorrect 20 ms 7020 KB wrong parameter
7 Incorrect 40 ms 7600 KB wrong parameter
8 Incorrect 13 ms 5252 KB too many decode_bit() calls
9 Incorrect 16 ms 5252 KB too many decode_bit() calls
10 Incorrect 13 ms 5236 KB wrong parameter
11 Incorrect 17 ms 5372 KB too many decode_bit() calls
12 Incorrect 12 ms 5168 KB too many decode_bit() calls
13 Incorrect 43 ms 7052 KB wrong parameter
14 Incorrect 13 ms 5256 KB too many decode_bit() calls
15 Incorrect 15 ms 5164 KB wrong parameter
16 Incorrect 32 ms 5788 KB too many decode_bit() calls
17 Incorrect 32 ms 5708 KB wrong parameter
18 Incorrect 40 ms 6228 KB wrong parameter
19 Incorrect 26 ms 6084 KB wrong parameter
20 Incorrect 47 ms 7240 KB too many decode_bit() calls
21 Incorrect 61 ms 7000 KB wrong parameter
22 Incorrect 46 ms 7512 KB wrong parameter
23 Incorrect 63 ms 8176 KB too many decode_bit() calls

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 11932 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 100 call(s) of encode_bit()
3 Incorrect 16 ms 6280 KB wrong parameter
4 Correct 3 ms 4704 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 6892 KB wrong parameter
6 Incorrect 20 ms 7020 KB wrong parameter
7 Incorrect 40 ms 7600 KB wrong parameter
8 Incorrect 13 ms 5252 KB too many decode_bit() calls
9 Incorrect 16 ms 5252 KB too many decode_bit() calls
10 Incorrect 13 ms 5236 KB wrong parameter
11 Incorrect 17 ms 5372 KB too many decode_bit() calls
12 Incorrect 12 ms 5168 KB too many decode_bit() calls
13 Incorrect 43 ms 7052 KB wrong parameter
14 Incorrect 13 ms 5256 KB too many decode_bit() calls
15 Incorrect 15 ms 5164 KB wrong parameter
16 Incorrect 32 ms 5788 KB too many decode_bit() calls
17 Incorrect 32 ms 5708 KB wrong parameter
18 Incorrect 40 ms 6228 KB wrong parameter
19 Incorrect 26 ms 6084 KB wrong parameter
20 Incorrect 47 ms 7240 KB too many decode_bit() calls
21 Incorrect 61 ms 7000 KB wrong parameter
22 Incorrect 46 ms 7512 KB wrong parameter
23 Incorrect 63 ms 8176 KB too many decode_bit() calls

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 11932 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 100 call(s) of encode_bit()
3 Incorrect 16 ms 6280 KB wrong parameter
4 Correct 3 ms 4704 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 6892 KB wrong parameter
6 Incorrect 20 ms 7020 KB wrong parameter
7 Incorrect 40 ms 7600 KB wrong parameter
8 Incorrect 13 ms 5252 KB too many decode_bit() calls
9 Incorrect 16 ms 5252 KB too many decode_bit() calls
10 Incorrect 13 ms 5236 KB wrong parameter
11 Incorrect 17 ms 5372 KB too many decode_bit() calls
12 Incorrect 12 ms 5168 KB too many decode_bit() calls
13 Incorrect 43 ms 7052 KB wrong parameter
14 Incorrect 13 ms 5256 KB too many decode_bit() calls
15 Incorrect 15 ms 5164 KB wrong parameter
16 Incorrect 32 ms 5788 KB too many decode_bit() calls
17 Incorrect 32 ms 5708 KB wrong parameter
18 Incorrect 40 ms 6228 KB wrong parameter
19 Incorrect 26 ms 6084 KB wrong parameter
20 Incorrect 47 ms 7240 KB too many decode_bit() calls
21 Incorrect 61 ms 7000 KB wrong parameter
22 Incorrect 46 ms 7512 KB wrong parameter
23 Incorrect 63 ms 8176 KB too many decode_bit() calls

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 11932 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 100 call(s) of encode_bit()
3 Incorrect 16 ms 6280 KB wrong parameter
4 Correct 3 ms 4704 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 6892 KB wrong parameter
6 Incorrect 20 ms 7020 KB wrong parameter
7 Incorrect 40 ms 7600 KB wrong parameter
8 Incorrect 13 ms 5252 KB too many decode_bit() calls
9 Incorrect 16 ms 5252 KB too many decode_bit() calls
10 Incorrect 13 ms 5236 KB wrong parameter
11 Incorrect 17 ms 5372 KB too many decode_bit() calls
12 Incorrect 12 ms 5168 KB too many decode_bit() calls
13 Incorrect 43 ms 7052 KB wrong parameter
14 Incorrect 13 ms 5256 KB too many decode_bit() calls
15 Incorrect 15 ms 5164 KB wrong parameter
16 Incorrect 32 ms 5788 KB too many decode_bit() calls
17 Incorrect 32 ms 5708 KB wrong parameter
18 Incorrect 40 ms 6228 KB wrong parameter
19 Incorrect 26 ms 6084 KB wrong parameter
20 Incorrect 47 ms 7240 KB too many decode_bit() calls
21 Incorrect 61 ms 7000 KB wrong parameter
22 Incorrect 46 ms 7512 KB wrong parameter
23 Incorrect 63 ms 8176 KB too many decode_bit() calls