oj.uz

Submission #566121

# Submission time Handle Problem Language Result Execution time Memory
566121 2022-05-21T20:29:04 Z RealSnake Saveit (IOI10_saveit) C++14
0 / 100
 203 ms 11980 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(v2[x].begin(), v2[x].end());
    }
    for(int i = 1; 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 = 1; i < n; i++) {
        int x = 0;
        for(int j = 0; j < 10; j++) {
            if(decode_bit())
                x += (1 << j);
        }
        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 203 ms 11980 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
3 Incorrect 15 ms 6272 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 22 ms 6820 KB wrong parameter
6 Incorrect 26 ms 6984 KB wrong parameter
7 Incorrect 43 ms 7560 KB wrong parameter
8 Incorrect 16 ms 5264 KB too many decode_bit() calls
9 Incorrect 16 ms 5224 KB too many decode_bit() calls
10 Incorrect 13 ms 5240 KB wrong parameter
11 Incorrect 18 ms 5420 KB too many decode_bit() calls
12 Incorrect 13 ms 5120 KB too many decode_bit() calls
13 Incorrect 37 ms 6884 KB wrong parameter
14 Incorrect 13 ms 5244 KB too many decode_bit() calls
15 Incorrect 15 ms 5216 KB wrong parameter
16 Incorrect 36 ms 5708 KB too many decode_bit() calls
17 Incorrect 32 ms 5880 KB wrong parameter
18 Incorrect 39 ms 6212 KB wrong parameter
19 Incorrect 28 ms 6120 KB wrong parameter
20 Incorrect 50 ms 7064 KB too many decode_bit() calls
21 Incorrect 64 ms 7024 KB wrong parameter
22 Incorrect 38 ms 7456 KB wrong parameter
23 Incorrect 62 ms 8196 KB too many decode_bit() calls

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 11980 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
3 Incorrect 15 ms 6272 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 22 ms 6820 KB wrong parameter
6 Incorrect 26 ms 6984 KB wrong parameter
7 Incorrect 43 ms 7560 KB wrong parameter
8 Incorrect 16 ms 5264 KB too many decode_bit() calls
9 Incorrect 16 ms 5224 KB too many decode_bit() calls
10 Incorrect 13 ms 5240 KB wrong parameter
11 Incorrect 18 ms 5420 KB too many decode_bit() calls
12 Incorrect 13 ms 5120 KB too many decode_bit() calls
13 Incorrect 37 ms 6884 KB wrong parameter
14 Incorrect 13 ms 5244 KB too many decode_bit() calls
15 Incorrect 15 ms 5216 KB wrong parameter
16 Incorrect 36 ms 5708 KB too many decode_bit() calls
17 Incorrect 32 ms 5880 KB wrong parameter
18 Incorrect 39 ms 6212 KB wrong parameter
19 Incorrect 28 ms 6120 KB wrong parameter
20 Incorrect 50 ms 7064 KB too many decode_bit() calls
21 Incorrect 64 ms 7024 KB wrong parameter
22 Incorrect 38 ms 7456 KB wrong parameter
23 Incorrect 62 ms 8196 KB too many decode_bit() calls

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 11980 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
3 Incorrect 15 ms 6272 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 22 ms 6820 KB wrong parameter
6 Incorrect 26 ms 6984 KB wrong parameter
7 Incorrect 43 ms 7560 KB wrong parameter
8 Incorrect 16 ms 5264 KB too many decode_bit() calls
9 Incorrect 16 ms 5224 KB too many decode_bit() calls
10 Incorrect 13 ms 5240 KB wrong parameter
11 Incorrect 18 ms 5420 KB too many decode_bit() calls
12 Incorrect 13 ms 5120 KB too many decode_bit() calls
13 Incorrect 37 ms 6884 KB wrong parameter
14 Incorrect 13 ms 5244 KB too many decode_bit() calls
15 Incorrect 15 ms 5216 KB wrong parameter
16 Incorrect 36 ms 5708 KB too many decode_bit() calls
17 Incorrect 32 ms 5880 KB wrong parameter
18 Incorrect 39 ms 6212 KB wrong parameter
19 Incorrect 28 ms 6120 KB wrong parameter
20 Incorrect 50 ms 7064 KB too many decode_bit() calls
21 Incorrect 64 ms 7024 KB wrong parameter
22 Incorrect 38 ms 7456 KB wrong parameter
23 Incorrect 62 ms 8196 KB too many decode_bit() calls

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 11980 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
3 Incorrect 15 ms 6272 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 22 ms 6820 KB wrong parameter
6 Incorrect 26 ms 6984 KB wrong parameter
7 Incorrect 43 ms 7560 KB wrong parameter
8 Incorrect 16 ms 5264 KB too many decode_bit() calls
9 Incorrect 16 ms 5224 KB too many decode_bit() calls
10 Incorrect 13 ms 5240 KB wrong parameter
11 Incorrect 18 ms 5420 KB too many decode_bit() calls
12 Incorrect 13 ms 5120 KB too many decode_bit() calls
13 Incorrect 37 ms 6884 KB wrong parameter
14 Incorrect 13 ms 5244 KB too many decode_bit() calls
15 Incorrect 15 ms 5216 KB wrong parameter
16 Incorrect 36 ms 5708 KB too many decode_bit() calls
17 Incorrect 32 ms 5880 KB wrong parameter
18 Incorrect 39 ms 6212 KB wrong parameter
19 Incorrect 28 ms 6120 KB wrong parameter
20 Incorrect 50 ms 7064 KB too many decode_bit() calls
21 Incorrect 64 ms 7024 KB wrong parameter
22 Incorrect 38 ms 7456 KB wrong parameter
23 Incorrect 62 ms 8196 KB too many decode_bit() calls