oj.uz

Submission #566132

# Submission time Handle Problem Language Result Execution time Memory
566132 2022-05-21T21:10:29 Z RealSnake Saveit (IOI10_saveit) C++14
0 / 100
 218 ms 12316 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);
    int 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 && i; 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]) {
                s.insert(j);
                if(j <= i)
                    continue;
                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);
    }
    int ans[n][h];
    for(int i = 0; i < h; i++) {
        ans[i][i] = ans[0][i] = 0;
        for(int j = 0; j < 10 && i; j++) {
            if(decode_bit())
                ans[0][i] += (1 << j);
        }
        set<int> s;
        s.insert(0);
        while(s.size()) {
            int x = *s.begin();
            s.erase(s.begin());
            if(x >= i) {
                hops(i, x, ans[x][i]);
                if(x < h && x != i)
                    hops(x, i, ans[x][i]);
            }
            for(int j : v[x]) {
                s.insert(j);
                if(j <= i)
                    continue;
                int dif = decode_bit();
                if(dif) {
                    if(!decode_bit())
                        dif = -1;
                }
                ans[j][i] = ans[i][j] = ans[x][i] + dif;
            }
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 12316 KB Output isn't correct
2 Correct 2 ms 4496 KB Output is correct - 75 call(s) of encode_bit()
3 Incorrect 34 ms 6740 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 95 call(s) of encode_bit()
5 Incorrect 40 ms 7356 KB Output isn't correct
6 Incorrect 41 ms 7492 KB Output isn't correct
7 Incorrect 53 ms 8040 KB Output isn't correct
8 Incorrect 41 ms 5816 KB Output isn't correct
9 Incorrect 30 ms 5840 KB Output isn't correct
10 Incorrect 39 ms 5876 KB Output isn't correct
11 Incorrect 37 ms 6200 KB Output isn't correct
12 Correct 29 ms 5728 KB Output is partially correct - 81008 call(s) of encode_bit()
13 Incorrect 60 ms 7536 KB Output isn't correct
14 Incorrect 37 ms 5892 KB Output isn't correct
15 Incorrect 33 ms 5864 KB Output isn't correct
16 Incorrect 56 ms 6408 KB Output isn't correct
17 Incorrect 60 ms 6520 KB Output isn't correct
18 Incorrect 54 ms 6900 KB Output isn't correct
19 Incorrect 44 ms 6432 KB Output isn't correct
20 Incorrect 68 ms 7704 KB Output isn't correct
21 Incorrect 79 ms 7520 KB Output isn't correct
22 Incorrect 54 ms 7936 KB Output isn't correct
23 Incorrect 72 ms 8704 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 12316 KB Output isn't correct
2 Correct 2 ms 4496 KB Output is correct - 75 call(s) of encode_bit()
3 Incorrect 34 ms 6740 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 95 call(s) of encode_bit()
5 Incorrect 40 ms 7356 KB Output isn't correct
6 Incorrect 41 ms 7492 KB Output isn't correct
7 Incorrect 53 ms 8040 KB Output isn't correct
8 Incorrect 41 ms 5816 KB Output isn't correct
9 Incorrect 30 ms 5840 KB Output isn't correct
10 Incorrect 39 ms 5876 KB Output isn't correct
11 Incorrect 37 ms 6200 KB Output isn't correct
12 Correct 29 ms 5728 KB Output is partially correct - 81008 call(s) of encode_bit()
13 Incorrect 60 ms 7536 KB Output isn't correct
14 Incorrect 37 ms 5892 KB Output isn't correct
15 Incorrect 33 ms 5864 KB Output isn't correct
16 Incorrect 56 ms 6408 KB Output isn't correct
17 Incorrect 60 ms 6520 KB Output isn't correct
18 Incorrect 54 ms 6900 KB Output isn't correct
19 Incorrect 44 ms 6432 KB Output isn't correct
20 Incorrect 68 ms 7704 KB Output isn't correct
21 Incorrect 79 ms 7520 KB Output isn't correct
22 Incorrect 54 ms 7936 KB Output isn't correct
23 Incorrect 72 ms 8704 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 12316 KB Output isn't correct
2 Correct 2 ms 4496 KB Output is correct - 75 call(s) of encode_bit()
3 Incorrect 34 ms 6740 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 95 call(s) of encode_bit()
5 Incorrect 40 ms 7356 KB Output isn't correct
6 Incorrect 41 ms 7492 KB Output isn't correct
7 Incorrect 53 ms 8040 KB Output isn't correct
8 Incorrect 41 ms 5816 KB Output isn't correct
9 Incorrect 30 ms 5840 KB Output isn't correct
10 Incorrect 39 ms 5876 KB Output isn't correct
11 Incorrect 37 ms 6200 KB Output isn't correct
12 Correct 29 ms 5728 KB Output is partially correct - 81008 call(s) of encode_bit()
13 Incorrect 60 ms 7536 KB Output isn't correct
14 Incorrect 37 ms 5892 KB Output isn't correct
15 Incorrect 33 ms 5864 KB Output isn't correct
16 Incorrect 56 ms 6408 KB Output isn't correct
17 Incorrect 60 ms 6520 KB Output isn't correct
18 Incorrect 54 ms 6900 KB Output isn't correct
19 Incorrect 44 ms 6432 KB Output isn't correct
20 Incorrect 68 ms 7704 KB Output isn't correct
21 Incorrect 79 ms 7520 KB Output isn't correct
22 Incorrect 54 ms 7936 KB Output isn't correct
23 Incorrect 72 ms 8704 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 12316 KB Output isn't correct
2 Correct 2 ms 4496 KB Output is correct - 75 call(s) of encode_bit()
3 Incorrect 34 ms 6740 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 95 call(s) of encode_bit()
5 Incorrect 40 ms 7356 KB Output isn't correct
6 Incorrect 41 ms 7492 KB Output isn't correct
7 Incorrect 53 ms 8040 KB Output isn't correct
8 Incorrect 41 ms 5816 KB Output isn't correct
9 Incorrect 30 ms 5840 KB Output isn't correct
10 Incorrect 39 ms 5876 KB Output isn't correct
11 Incorrect 37 ms 6200 KB Output isn't correct
12 Correct 29 ms 5728 KB Output is partially correct - 81008 call(s) of encode_bit()
13 Incorrect 60 ms 7536 KB Output isn't correct
14 Incorrect 37 ms 5892 KB Output isn't correct
15 Incorrect 33 ms 5864 KB Output isn't correct
16 Incorrect 56 ms 6408 KB Output isn't correct
17 Incorrect 60 ms 6520 KB Output isn't correct
18 Incorrect 54 ms 6900 KB Output isn't correct
19 Incorrect 44 ms 6432 KB Output isn't correct
20 Incorrect 68 ms 7704 KB Output isn't correct
21 Incorrect 79 ms 7520 KB Output isn't correct
22 Incorrect 54 ms 7936 KB Output isn't correct
23 Incorrect 72 ms 8704 KB wrong parameter